G Ost

P Reynaud-Bouret

SPARSE SPACE-TIME MODELS: CONCENTRATION INEQUALITIES AND LASSO

Keywords: MSC 2010 subject classifications:, Restricted eigenvalue, Chains of infinite order, Perfect Simulation, Concentration inequalities, Oracle inequalities, Lasso Estimator, Stochastic neuronal networks

Inspired by Kalikow-type decompositions, we introduce a new stochastic model of infinite neuronal networks, for which we establish sharp oracle inequalities for Lasso methods and restricted eigenvalue properties for the associated Gram matrix with high probability. These results hold even if the network is only partially observed. The main argument rely on the fact that concentration inequalities can easily be derived whenever the transition probabilities of the underlying process admit a sparse space-time representation.

1. Introduction. Lasso-type methods in classic regression settings assume that the corresponding Gram matrix G fulfills nice properties such as the Restricted Isometry Property (RIP), Restricted Eigenvalue (RE) conditions, etc. In many works (see for instance van de Geer and [START_REF] Van De Geer | On the conditions used to prove oracle results for the Lasso[END_REF]; [START_REF] Bühlmann | Statistics for High-Dimensional Data: Methods, Theory and Applications[END_REF]; van de Geer ( 2016) and references therein), the explanatory variables involved in the Gram matrix are given at first and it is natural to define the regression model conditionally to these variables. In this sense, it is also natural to assume such properties on the Gram matrix G without trying to show that they are fulfilled with high probability. In practice, it is computationally difficult to check whether G satisfies or not these assumptions and many works have shown how random matrices can fulfill such properties with high probability (see for instance [START_REF] Candès | Decoding by linear programming[END_REF]; [START_REF] Rudelson | On sparse reconstruction from Fourier and Gaussian measurements[END_REF] or the references in [START_REF] Tropp | Sampling Theory, a Renaissance: Compressive sampling and other developments Convex recovery of a structured signal from independent random linear measurements[END_REF]).

However, in several probabilistic frameworks it is difficult to separate the study of the Gram matrix from the study of the process itself (see for instance [START_REF] Kock | Oracle inequalities for high dimensional vector autoregressions[END_REF] where the probabilistic framework is of auto-regressive kind or [START_REF] Gaïffas | Sparse inference of the drift of a high-dimensional Ornstein-Uhlenbeck process[END_REF] for Markovian continuous processes). Several works have therefore shown that with high probability, Lasso or other adaptive methods satisfy oracle inequalities or minimax results and that, on the same event, the corresponding Gram matrix (which is considered here also as a random variable) satisfies RIP or RE (see for instance [START_REF] Kock | Oracle inequalities for high dimensional vector autoregressions[END_REF]; [START_REF] Basu | Regularized Estimation in Sparse High-dimensional Time Series Models[END_REF]; [START_REF] Jiang | Minimax optimal rates for poisson inverse prob-lems with physical constraints[END_REF]; [START_REF] Hunt | A datadependent weighted LASSO under Poisson noise[END_REF]).

We are here interested in a particular type of stochastic process that can model the spiking events of a possibly infinite network of neurons. Many probabilistic models of neuronal activities in a network exist. As examples, let us cite continuous frameworks where both the voltage and the spiking activity of each neuron are modeled (see for instance [START_REF] Sacerdote | Stochastic Biomathematical Models 2058 Stochastic Integrate and Fire Models: A Review on Mathematical Methods and Their Applications[END_REF]), or where the spike trains are directly modeled by point processes (see e.g Chevallier ( 2015) ). There are also approaches, closer to the present one, where discrete time is used (see [START_REF] Cofré | Exact computation of the maximum-entropy potential of spiking neuralnetwork models[END_REF]; [START_REF] Galves | Modeling networks of spiking neurons as interacting processes with memory of variable length[END_REF]).

Although many statistical methods have been developed to estimate the probability to spike given the past for various probabilistic models, most of the time one assumes that the network is fully observed (see for instance [START_REF] Pouzat | Automatic spike train analysis and report generation. An implementation with R, R2HTML and STAR[END_REF] on Wold processes, [START_REF] Chen | The Multivariate Hawkes Process in High Dimensions: Beyond Mutual Excitation[END_REF] on Hawkes processes or [START_REF] Mark | Network estimation from point process data[END_REF] on Poisson counts). Let us underline the work by [START_REF] Hansen | Lasso and probabilistic inequalities for multivariate point processes[END_REF], which is the closest to ours from a statistical point of view, in which the authors applied a Lasso method on point processes and derived an oracle inequality on an event where the corresponding Gram matrix G is invertible. In a second step, the authors have shown that G is invertible with high probability when the observed process is a linear Hawkes process and the small fixed number of observed neurons correspond in fact to the totality of the network (see also [START_REF] Kelly | Accounting for network effects in neuronal responses using L1 regularized point process models[END_REF] for an application on real data of Lasso-type methods). However, in practice, data biologists record are much more scarce than a complete recordings of the whole network activity. Most of the time, just few tens of neurons are recorded and they correspond to neurons that are embedded in at least a network of thousands of neurons.

We are aware of only two articles which clearly deal more deeply with the problem of partial observation from a mathematical point of view : [START_REF] Lerasle | Sharp oracle inequalities and slope heuristic for specification probabilities estimation in general random fields[END_REF] and [START_REF] Duarte | Estimating the interaction graph of stochastic neural dynamics[END_REF]. In [START_REF] Lerasle | Sharp oracle inequalities and slope heuristic for specification probabilities estimation in general random fields[END_REF], the authors assume that the configuration describing the neural activity follows a Gibbsian distribution, which does not take dependency in time into account, fact which is of the utmost importance in neuroscience. In [START_REF] Duarte | Estimating the interaction graph of stochastic neural dynamics[END_REF], the interaction neighborhood of a given neuron is estimated by assuming that we observe more neurons than this neighborhood even if it is not the totality of network. In practice, the complexity of the algorithm makes it difficult to apply it on large data sets. In these two works, the purpose is clearly to deal with the fact that some neurons (or nodes of the network) are not recorded at all whereas the recordings are complete for the observed neurons. In a slightly different statistical setting, note also the work by [START_REF] Mark | Estimating Network Structure from Incomplete Event Data[END_REF], which deals with another kind of missing data, the applied filter being i.i.d. in both time and nodes but without nodes that are completely unrecorded.

The aim of the present work is to show that with high probability, the Gram matrix G satisfies nice properties such as invertibility or RE condition with as few assumptions as possible on the underlying probabilistic models and this even if we observe only a small number of neurons embedded in an infinite neuronal network , for which most of the neurons are not observed at all.

Inspired by [START_REF] Galves | Infinite Systems of Interacting Chains with Memory of Variable Length-A Stochastic Model for Biological Neural Nets[END_REF] model and Kalikow-type decompositions (see [START_REF] Kalikow | Random markov processes and uniform martingales[END_REF]; Galves et al. (2013)), we consider discrete time models for which the prob-ability of a neuron to spike at a given time unit given the past configuration may only depend on a few neurons (assimilated to space positions) and few time steps. Hence the dependencies in time and space should be very small but may be random and chosen at each step. We use this probabilistic sparsity in time and space to prove concentration inequalities for various functionals including Gram matrices. We employ these concentration inequalities to prove that RE properties are satisfied with large probability even on a partially observed infinite network. Therefore we show that Lasso methods have good theoretical properties even in this case.

The paper is organized as follows. In Section 2, we provide the main notation and present briefly the stochastic framework with its main assumptions. In Section 3, we prove an oracle inequality for the Lasso estimator of the transition probabilities of this model. The oracle inequality is derived on a certain event on which some properties of the Gram matrix are met. Examples of useful dictionaries are also presented in this section. We discuss, in Section 4, the definition of space-time decomposition and show examples of discrete time models where it applies. Besides, thanks to the definition of a simulation algorithm inspired by [START_REF] Galves | Infinite Systems of Interacting Chains with Memory of Variable Length-A Stochastic Model for Biological Neural Nets[END_REF], we prove that stochastic models admitting a space-time decomposition have a stationary version even on infinite networks under some conditions of probabilistic sparsity. We prove that these conditions are usually much less stringent than the ones of the literature. Still in the same section, we obtain concentration inequalities for such processes, under some additional exponential constraints, by adapting arguments of Viennet (1997). This allows us to prove that the introduced Gram matrices based on a partial observation of the network are invertible or satisfy RE with high probability. This is done in Section 5. A brief conclusion is given in Section 6. All proofs are given in the Section 7.

2. Stochastic framework and notation. We write N to denote the set of natural numbers {0, 1, 2, . . .}. The sets of integers {. . . , -1, 0, 1, . . .} is denoted by Z. The set of strictly negative and positive integers are denoted by Z -and Z + respectively.

We consider a stationary stochastic chain X = (X i,t ) i∈I,t∈Z taking values in {0, 1} I×Z , defined on a probability space (Ω, F, P), where I is a countable (possibly infinite) set. The set I represents the set of neurons in the network. For each i ∈ I and t ∈ Z,

X i,t = 1, if neuron i spikes at time t, 0, otherwise.
The configuration of X at time t ∈ Z is denoted by X t = (X i,t , i ∈ I). For s, t ∈ Z with s < t, X i,s:t stands for the collection (X i,s , . . . , X i,t ) and X s:t for the collection (X i,r ) i∈I,s≤r≤t . For each t ∈ Z, X -∞:t denotes the past history (. . . , X t-1 , X t ) of X at time t + 1. Note that the past histories have space-time components. For F ⊂ I and t ∈ Z, X F,t = (X i,t , i ∈ F ) denotes the configuration of X at time t restricted to set F . More generally, for any subset v ⊂ I × Z, X v denotes the collection (X i,t ) (i,t)∈v .

Assumption 1. For each t ∈ Z, given the past history X -∞:t , the neurons spike independently of each other at time t + 1, i.e., for any finite set J ⊂ I and (a i ) i∈J ∈ {0, 1} J ,

P(∩ i∈J {X i,t+1 = a i }|X -∞:t = x) = i∈J P(X i,t+1 = a i |X -∞:t = x) P-a.e. x ∈ {0, 1} I×Z -.
Since the stochastic chain X is stationary, Assumption 1 implies that the dynamics of X is fully characterized by the transition probabilities

p i (x) = P(X i,0 = 1|X -∞:-1 = x), x ∈ {0, 1} I×Z -, i ∈ I.
These transition probabilities are all assumed to be measurable functions of x ∈ {0, 1} I×Z -.

Hereafter, we need the following notation. For any neighborhood v ⊂ I × Z -and x, y ∈ {0, 1} I×Z -, we write

x v = y to indicate y v = x v . For any real-valued function f on {0, 1} I×Z - and subset v ⊂ I × Z -, we say f is cylindrical in v and write f (x) = f (x v ), if f (x) = f (y) for any x, y ∈ {0, 1} I×Z -such that x v = y.
Let us now present briefly the three other main probabilistic assumptions that we may require in the article. They will be discussed in more details in the sequel.

We denote by V the collection of finite neighborhoods, i.e. finite subsets of I × Z -and we consider processes for which the following decomposition holds.

Assumption 2 (Space-time decomposition). For all v in V and i in I, there exists a [0, 1]-valued measurable function p v i (.), cylindrical in v, and a non negative weight λ i (v), such that for all x ∈ {0, 1} I×Z -and i ∈ I,

   p i (x) = λ i (∅)p ∅ i (x) + v∈V,v =∅ λ i (v)p v i (x), v∈V λ i (v) = 1.
As we will see in Section 4 where we discuss in details the implication of this assumption, this Kalikow-like assumption is actually met by a wide variety of stochastic processes modeling neuronal networks.

For all neighborhood v ∈ V, let T (v) = -min(s ∈ Z -, (j, s) ∈ v) be the corresponding time length, with the convention that T (∅) = 0. We also assume the following.

Assumption 3. There exists a strictly positive θ such that for all i,

ϕ i (θ) = v∈V |v|e θT (v) λ i (v) is finite and (2.1) ϕ(θ) = sup i∈I ϕ i (θ) < 1.
This assumption, which can be seen as probabilistic sparsity (see Section 4), means that the neighborhoods used in the previous decomposition are in average nor too large neither too timely spread.

Finally, we will use also the following assumption to control the Gram matrices in Section 5.

Assumption 4. There exists some positive µ such that for all i ∈ I, for all x,

µ ≤ p i (x) ≤ 1 -µ,
This means that whatever the past, there is always enough randomness in the system. Note that all these 4 assumptions are very general and are there to control the randomness of the underlying neuronal system without specifying any parametric models. In particular in what follows, the p i 's are just approximated by a finite combination of elements of dictionaries, without being one (see Section 3): the overall purpose is to approximate p i by what happens in a finite subset of observed neurons, namely F , always keeping in mind that F is embedded in a much more complex and potentially infinite network I, the overall complex stochastic interactions inside I being governed by Assumptions 1, 2, 3 and/or 4 depending on the results.

3. Lasso method and statistical notation. For a finite F ⊂ I, subset of observed neurons, and integers T > m ≥ 1 measuring the observation window, the aim is to estimate x → p i (x) for a fixed neuron i ∈ F , given the sample X F,-(m-1):T . To that end, for each time 1 ≤ t ≤ T , we compare the past X F,(t-m):(t-1) to the current observation X i,t to guess what can be a good approximation of p i (x). The intuition behind this strategy is that for a well-chosen space-time neighborhood v ⊂ I × Z -, it might be sufficient to know x v and not the whole past configuration x to well approximate p i (x).

Given the sample X F,-(m-1):T , one might consider several candidates to approximate p i (x). Here, we shall approximate p i (x) by linear combinations of a given dictionary Φ, i.e. a finite set of real-valued functions on {0, 1} I×Z -which are cylindrical in F × m with m = {-m, . . . , -1}. More precisely, for each vector a = (a ϕ ) ϕ∈Φ ∈ R Φ , we denote

(3.1) x → f a (x) = ϕ∈Φ a ϕ ϕ(x),
the candidate encoded by the vector a that should approximate p i (x). We assume that the functions in the dictionary are bounded in infinite norm by Φ ∞ . We use the least-square contrast defined by

C(f a ) = - 2 T T t=1 f a (X F,(t-m):(t-1) )X i,t + 1 T T t=1 f 2 a (X F,(t-m):(t-1) ), a = (a ϕ ) ϕ∈Φ ∈ R Φ .
Observe that if for real-valued functions f and g on {0, 1} I×Z -, we denote f, g T =

1 T T -1 t=0 f (X -∞:t )g(X -∞:t
) and f T the corresponding norm, then one has

C(f a ) = -2 f a , X i,•+1 T + f a 2 T = f a -X i,•+1 2 T -X i,•+1 2 T ,
and C is minimum when f a -X i,.+1 2 T is minimum. In this sense, minimizing C over functions that are only depending on the past might give a good estimator of p i (x).

Notice also that, if for ϕ, ϕ ∈ Φ we write, (3.2)

b ϕ = 1 T T t=1 ϕ(X F,(t-m):(t-1) )X i,t and G ϕ,ϕ = 1 T T t=1 ϕ(X F,(t-m):(t-1) )ϕ (X F,(t-m):(t-1) ),
then C(f a ) can be rewritten as -2a b + a Ga,

where b = (b ϕ , ϕ ∈ Φ) is a vector of R Φ , G = (G ϕ,ϕ ) ϕ,ϕ
∈Φ is the Gram matrix and a is the transpose of vector a.

In the sequel, let |a| = (|a ϕ |, ϕ ∈ Φ), |a| ∞ = max ϕ∈Φ |a ϕ |, a = √ a a and |a| 1 = 1 |a| where 1 is the vector with all coordinates equal to 1.

Following [START_REF] Hansen | Lasso and probabilistic inequalities for multivariate point processes[END_REF], we minimize C(f a ) subject to a 1 -penalization on the vector a = (a ϕ , ϕ ∈ Φ). Precisely, we choose the function f = f â where

(3.3) â ∈ arg min a∈R Φ {-2a b + a Ga + γd|a|} ,
for d a positive term controlling the random fluctuations and γ > 0, a tuning parameter. The active set S(a) of a vector a ∈ R Φ is the set S(a) = {ϕ : a ϕ = 0}. We shall denote for any subset J ⊂ Φ and any a ∈ R Φ , a J ∈ R Φ the vector whose coordinates in J are equal to the ones of a and 0 anywhere else. We also denote by |J| the cardinality of J.

For later use, let us write for each ϕ ∈ Φ,

(3.4) bϕ = 1 T T -1 t=0 ϕ(X F,t-m:t )p i (X -∞:t ).
3.1. Examples of dictionaries. Let us present briefly some examples of dictionaries that might be useful.

Short memory effect. Let the dictionary Φ be defined by the set {ϕ j : j ∈ F } where

ϕ j (x) = 1, if x j,s = 1 for some -m ≤ s ≤ -1 0, otherwise , x ∈ {0, 1} I×Z -,
so that we are trying to explain the presence of a spike on neuron i at time t by a linear combination of the presence of a spike on neuron j in a small window just before time t.

Cumulative effect. We can also think that m = ηL is a much larger parameter and cut the past m into L small pieces of length η, where the effect of the spikes are different and cumulative. This leads to the dictionary Φ defined by the set {ϕ j, : j ∈ F and 1 ≤ ≤ L} where

ϕ j, (x) = -η( -1)-1 s=-η x j,s , x ∈ {0, 1} I×Z -.
Cumulative effect with spontaneous apparition. It can be important to take into account a background activity, especially to explain the apparition of spikes due to the unobserved part of the network. To do so, we may add to the previous dictionary an extra function

ϕ 0 = 1,
whose corresponding coefficient corresponds to a spontaneous activity.

Hawkes dictionary. In both the cumulative effect and the cumulative effect with spontaneous part, one might be interested in a particular example where η = 1 and L = m. In particular, in the case with spontaneous part, we are therefore interested in approximating

p i (x) by f a (x) = a 0 + j∈F -m≤s≤-1 a j,-s x j,s , x ∈ {0, 1} I×Z -,
which is the exact form of a discrete Hawkes process restricted to F × m (see Section 4) and this even if p i is not of this shape. Note that whatever the dictionary, m represents the maximal delay in the dictionary and |F | the number of observed neurons. As we will see in Section 5, both these quantities have to be usually less than a certain increasing function of T , which depends on the dictionary (typically log(T )), to derive an RE property on the Gram matrix. In particular |m| might grow slightly with T to ensure a good asymptotic approximation of the dependency in time. Mathematically speaking, the same holds for |F |, although the size of F is dictated by the neurophysiological experiment and, for practical prupose, it is always thought to be a constant with respect to T .

Oracle inequality.

It is classical, by now, to derive oracle inequalities for Lasso procedures if G satisfies some properties. We use two of them.

Definition 1. Let κ > 0. The matrix G satisfies Property Inv(κ) if ∀a ∈ R Φ , a Ga ≥ κ a 2
A weaker version is the restricted eigenvalue condition.

Definition 2. Let c > 0, κ > 0 and s ∈ N. The matrix G satisfies Property RE(κ, c, s) if for all subset J such that |J| ≤ s and for all a ∈ R Φ such that

|a J c | 1 ≤ c|a J | 1 , the following holds a Ga ≥ κ a J 2 .
Our first result establish an oracle inequality for the estimator f = f â where â is defined by (3.3).

Theorem 1. Let γ ≥ 2, κ > 0 and s ∈ N. On the event on which

(i) for all ϕ ∈ Φ, |b ϕ -bϕ | ≤ d, (ii) and G satisfies RE(κ, c(γ), s) with c(γ) = γ+2
γ-2 , the following inequality is satisfied

(3.5) f -p i (•) 2 T ≤ inf a∈R Φ : |S(a)|≤s f a -p i (•) 2 T + κ -1 |S(a)|d 2 (γ + 2) 2 4 .
Moreover for any 0

< δ < 1, if d = d δ with d δ = Φ 2 ∞ log |Φ| + log(2δ -1 ) 2T , then P(∃ϕ ∈ Φ : |b ϕ -bϕ | > d) ≤ δ.
Equation (3.5) is a classical oracle inequality (see for instance [START_REF] Hansen | Lasso and probabilistic inequalities for multivariate point processes[END_REF] or [START_REF] Hunt | A datadependent weighted LASSO under Poisson noise[END_REF] for close set-ups). This result means that the Lasso estimator gives the best s-sparse approximation of p i based on the dictionary Φ and that the price to pay is of the order of κ -1 sd 2 , if we assume that Φ ∞ ≤ 1. With the choice d = d δ , we have therefore a price of the order of κ -1 s log |Φ|+log(2δ -1 ) T . Note that if we knew that p i can be indeed decomposed on Φ, meaning that the model is true and that in particular p i only depends on s elements of the dictionary Φ, the price to pay anyway to estimate p i would be roughly of the order of s/T . Therefore if the logarithmic factor is a classical loss for adaptation in (3.5), it remains to see the order of κ, to see if (3.5) gives roughly the best possible rate.

Note that if G satisfies Inv(κ) then one can choose γ = 2 and s = |Φ| in Theorem 1 and (3.5) can be rewritten as

f -p i (•) 2 T ≤ inf a∈R Φ f a -p i (•) 2 T + 4κ -1 |S(a)|d 2 ,
which is a sharper version of the result proved in [START_REF] Hansen | Lasso and probabilistic inequalities for multivariate point processes[END_REF] in continuous time, up to the fact that they used more general weights which leads to a weighted 1 norm in the criterion. The same refinement would have been possible but since the focus is here on the Gram matrix, we have decided to use a classical 1 norm for sake of simplicity. Note also that another (very easy) refinement consists in clipping f to ensure that it remains between 0 and 1. The same result holds for this clipped version. Another way to find similar results for estimators that are forced to be in [0, 1] is to use penalized maximum likelihood. Many works have used it (see for instance [START_REF] Mark | Network estimation from point process data[END_REF] for Poisson counts or [START_REF] Basu | Regularized Estimation in Sparse High-dimensional Time Series Models[END_REF]; [START_REF] Gaïffas | Sparse inference of the drift of a high-dimensional Ornstein-Uhlenbeck process[END_REF] in Gaussian Markovian set-ups). This comes with additional technicalities, in particular if the likelihood of the statistical model is not easy to compute, because the model is not Gaussian. In particular, Mark, Raskutti and Willett (2019) use a setting very close to ours, but simpler (see also the examples in Section 4) and make use of Taylor expansion to approximate the criteria. Translated here, the approximation would depend on the dictionary we use and would be more complex for each dictionary. Once again, because the focus is here on the Gram matrix, we have decided to stick with the simplest Lasso result made for least-square contrast.

Results for controlling Gram matrices are numerous (see for instance [START_REF] Basu | Regularized Estimation in Sparse High-dimensional Time Series Models[END_REF]; [START_REF] Gaïffas | Sparse inference of the drift of a high-dimensional Ornstein-Uhlenbeck process[END_REF]; [START_REF] Hunt | A datadependent weighted LASSO under Poisson noise[END_REF] for simpler settings than the present one) but always assume that the whole network is observed and that the target can be written on the dictionary. In [START_REF] Hansen | Lasso and probabilistic inequalities for multivariate point processes[END_REF], which is the closest framework to the present one, it has been proved for instance that, if one observes the whole finite network and if the spike trains are linear Hawkes processes, then G is invertible with large probability for well chosen dictionaries. In this case, the corresponding κ is roughly lower bounded by a quantity which is exponentially small in the total number of neurons in the network. Here we would like to go beyond these assumptions and prove that even if

• the model is wrong (i.e. p i is not Hawkes for instance) and p i cannot be written on the dictionary, • the network is infinite,

• we only observe a very partial subnetwork, it is still possible to find good κ with high probability and that the dependency in the number of neurons can be much better than these previous results.

The main idea consists in using very general Kalikow-type decomposition of the transition probabilty p i (x), that are available in discrete time (see Galves et al. (2013)) and that do not exist with such generality in continuous time (see however [START_REF] Hodara | Hawkes Processes with variable length memory and an infinite number of components[END_REF] for promising results in this direction).

Space-time decomposition and concentration.

4.1. Definition. Let us first recall Assumption 2: For all v in V and i in I, there exists a [0, 1]-valued measurable function p v i (.), cylindrical in v, and a non negative weight λ i (v), such that for all x ∈ {0, 1} I×Z -and i ∈ I,

   p i (x) = λ i (∅)p ∅ i (x) + v∈V,v =∅ λ i (v)p v i (x), v∈V λ i (v) = 1.
The aforementioned decomposition can be interpreted as follows. At each time step, to decide whether the neuron i spikes or not, we first choose a random space-time neighborhood V ∈ V according to the distribution λ i . Once this neighborhood V is chosen, we decide if a spike of neuron i occurs with probability p V i (x V ) that depends only on the past history restricted to V . Note that p ∅ i (x) does not depend on x at all, and we denote this value p ∅ i . Such a space-time decomposition of the transition probabilities {p i (x), i ∈ I, x ∈ {0, 1} I×Z -} generalizes the classical Kalikow decomposition introduced in [START_REF] Kalikow | Random markov processes and uniform martingales[END_REF] and further developed in [START_REF] Comets | Processes with long memory: Regenerative construction and perfect simulation[END_REF], Galves et al. (2013) and [START_REF] Galves | Infinite Systems of Interacting Chains with Memory of Variable Length-A Stochastic Model for Biological Neural Nets[END_REF]. The main difference consists in not forcing the nesting of the neighborhoods v that lie in the support of λ i . This helps us to exploit the fact that in many cases the distributions λ i charge very few neighborhoods and that the cardinality of this neighborhood is usually very small, if the nesting is not forced. We speak in this case of probabilistic sparsity.

Remark 1. If we denote q i (x) = P(X i,0 = 0|X -∞:-1 = x) = 1 -p i (x) and q v i (x) = 1 -p v i (x) for all i ∈ I, x ∈ {0, 1} I×Z -, we can also write

q i (x) = λ i (∅)q ∅ i (x) + v∈V,v =∅ λ i (v)q v i (x),
where for each v ∈ V, the function

q v i is cylindrical in v.
Remark 2. For a given space-time decomposition, one can use Remark 1 to deduce that for all i ∈ I, inf

x∈{0,1} I×Z - p i (x) + inf x∈{0,1} I×Z - q i (x) ≥ λ i (∅). More generally, for any v ∈ V, one can show that inf x∈{0,1} I×Z - inf y∈{0,1} I×Z -: y v = x p i (y) + inf y∈{0,1} I×Z -: y v = x q i (y) ≥ λ i (∅) + w⊆v,w =∅ λ i (w).
One can also show that the space-time decomposition is not unique. This fact raises the question of whether there is an "optimal" decomposition of a given transition probability. Such a question, however, is not discussed in this article.

Main examples.

4.2.1. Markov chains. Suppose I is a singleton, say I = {1}, and denote X t instead of X 1,t for convenience. Let us assume also that for all

x ∈ {0, 1} Z -, p(x) = P(X 0 = 1|X -∞:-1 = x) = P(X 0 = 1|X -1 = x -1 ),
that is, the stochastic chain X = (X t ) t∈Z is a Markov chain of order 1 taking values in {0, 1}. To shorten notation, let

p 1 = P(X t = 1|X t-1 = 1), q 1 = 1 -p 1 , p 0 = P(X t = 1|X t-1 = 0) and q 0 = 1 -p 0 .
We can always write the transition probability p(x) as

p(x) = p 1 x -1 + p 0 (1 -x -1 ).
Let us denote p = p 1 ∧ p 0 , q = q 1 ∧ q 0 and µ = p + q. If 0 < µ < 1, then one can write

p(x) = µ p µ + (1 -µ) p 1 -p 1 -µ x -1 + p 0 -p 1 -µ (1 -x -1 ) .
So one can use as space-time decomposition (4.1)

         λ(∅) = µ p ∅ = p µ λ({-1}) = 1 -µ p {-1} (x) = p 1 -p 1-µ x -1 + p 0 -p 1-µ (1 -x -1 )
.

Note that the support of λ is then reduced to {∅, {-1}}. Note also than it is quite straightforward to extend this to the multidimensional models considered in [START_REF] Mark | Estimating Network Structure from Incomplete Event Data[END_REF], for instance by saying that when the neighborhood is not empty, one picks I which is finite in their case.

4.2.2. Chains of infinite order. Again suppose I is a singleton. In this case, the stochastic chain X is described by the transition probability {p(x), x ∈ {0, 1} Z -}. Denote for ∈ Z + , the set {-, ..., -1} and

β = sup x∈{0,1} Z - sup y, z ∈ {0, 1} Z -s.t. y = z = x {|p(y) -p(z)|}.
If there exist 0 ≥ 1 such that β = 0 for all ≥ 0 , then the stochastic chain X is called Markov Chain of Order 0 . Otherwise, X is called Chain of Infinite Order. We refer the reader to [START_REF] Fernandéz | Coupling, renewal and perfect simulation of chains of infinite order[END_REF] for a comprehensive introduction to Chains of Infinite Order.

If β → 0 as → ∞, then {p(x), x ∈ {0, 1} Z -} is said to be continuous and the sequence (β ) ∈Z + is called the continuity rate. Recall that q(x) = 1 -p(x) for all x ∈ {0, 1} Z -. One can then compute for ∈ Z + ,

α( ) = inf x∈{0,1} Z - inf y∈{0,1} Z -s.t. y =x p(y) + inf y∈{0,1} Z -s.t. y =x q(y) .
This allows us to define the distribution λ which has support only on the 's and

(4.2) λ( ) = α( ) -α( -1),
where

α(0) = λ(∅) = inf x∈{0,1} Z -p(x) + inf x∈{0,1} Z -q(x).
One can show that every continuous transition probability {p(x), x ∈ {0, 1} Z -} admits a decomposition of the form:

(4.3) p(x) = λ(∅)p ∅ + ∈Z + λ( )p (x) λ(∅) + ∈Z + λ( ) = 1 . Moreover (4.3) is a space-time decomposition since p ∅ ∈ [0, 1] and for each ∈ Z + , {p (x), x ∈ {0, 1} Z -}
is a transition probability of a Markov chain of order . 4.2.3. Discrete-time linear Hawkes processes. Multivariate Hawkes processes (also referred in the neuroscience literature as a particular case of generalized linear models) are often used to model interacting spike trains and especially the synaptic integration. In contrast to the classical framework where these processes are described in continuous time and are not linear, we focus here on a discrete-time and linear formulation, where for i ∈ I :

(4.4) ψ i (x) = ν i + s∈Z -j∈I
h j→i (-s)x j,s , and

     p i (x) = ψ i (x), if ψ i (x) ∈ [0, 1], p i (x) = 1, if ψ i (x) > 1, p i (x) = 0, if ψ i (x) < 0.
In this formula, ν i ≥ 0 represents the spontaneous activity of neuron i, that is its ability to produce spikes when there is no interaction. The interaction function h j→i measures the amount of excitation (if positive) or inhibition (if negative) that a spike of neuron j has on neuron i after a delay -s (a spike of neuron j with delay -s corresponds to x j,s = 1). For a given neuron i ∈ I, we write

A + i = {(j, s) ∈ I × Z -: h j→i (-s) > 0} and A - i = {(j, s) ∈ I × Z -: h j→i (-s) < 0},
and define the maximal excitatory (respectively inhibitory) strength by

Σ + i = (j,s)∈A + i |h j→i (-s)| and Σ - i = (j,s)∈A - i |h j→i (-s)|.
Let us assume that

(4.5) 0 ≤ ν i -Σ - i and ν i + Σ + i ≤ 1,
which implies in particular that whatever the past configuration x ∈ {0, 1} I×Z -, the transition probability p i (x) ∈ [0, 1] is always equal to ψ i (x). It also implies that

Σ + i + Σ - i ∈ [0, 1].
Then one can use for the space-time decomposition:

(4.6)                λ i (∅) = 1 -(Σ + i + Σ - i ) which is ≥ 0 since 0 ≤ Σ + i + Σ - i ≤ 1, p ∅ i = ν i -Σ - i λ i (∅) which is ≤ 1 since ν i + Σ + i ≤ 1, λ i ({(j, s)}) = |h j→i (-s)| for all (j, s) ∈ A + i ∪ A - i , p {(j,s)} i (x) = x j,s for all (j, s) ∈ A + i , p {(j,s)} i (x) = (1 -x j,s ) for all (j, s) ∈ A - i .
It is moreover sufficient to assume that Σ + i + Σ - i < 1 to have λ i (∅) > 0. The discrete-time linear Hawkes model is an interesting example, because even if the true interaction graph, that is the set of edges (j, i) ∈ I×I for which h j→i is non zero, is complete, the random neighborhoods V ∈ V of the space-time decomposition have cardinality at most 1 almost surely. This probabilistic sparsity is exploited in the sequel to obtain concentration inequalities.

Note that it is classically assumed for general Hawkes models that the spectral radius of the matrix ( |h j→i |) i,j is smaller than 1 to ensure stationnarity of the whole multivariate process. Here this matrix can be reinterpreted as H = ( >1 |h j→i ( )|) i,j . Therefore (4.5) is different from the usual assumption: it implies in particular that Σ + + Σ -= H1 ≤ 1 coordinate per coordinate where Σ + = (Σ + i ) i , Σ + = (Σ + i ) i and 1 is the vector of 1's.

4.2.4. GL neuron model. Let W j→i ∈ R with i, j ∈ I, be a collection of real numbers such that W j→j = 0 for all j. For each i ∈ I, let ϕ i : R → [0, 1] be a non-decreasing measurable function and g i = (g i ( )) ∈Z + be a sequence of strictly positive real numbers. Here, W j→i is interpreted as the synaptic weight of neuron j on neuron i, ϕ i as the spike rate function of neuron i and g i as the postsynaptic current pulse of neuron i.

For each x ∈ {0, 1} I×Z -and i ∈ I, we define L i (x) = sup{s ∈ Z -: x i,s = 1}. The stochastic chain X satisfies a GL neuron model if the transition probabilities {p i (x), i ∈ I, x ∈ {0, 1} I×Z -} are given by (see [START_REF] Galves | Infinite Systems of Interacting Chains with Memory of Variable Length-A Stochastic Model for Biological Neural Nets[END_REF]

) (4.7) p i (x) = ϕ i (0), if L i (x) = -1, ϕ i j∈I W j→i -1 s=L i (x)+1 g j (-s)x j,s , otherwise.
Remark 3. Notice that the functions L i 's introduce a structure of variable-length memory in the model. For this reason the GL neuron model was introduced in Galves and Löcherbach (2013) under the name of Systems of Interacting Chains with Memory of Variable Length.

Linear spike rate functions. Let us consider the particular case where the parameters of the model are such that ϕ i (u) = ν i + u with ν i ≥ 0 for each i ∈ I. Similarly to Section 4.2.3, let us denote for each i ∈ I,

A + i = {(j, s) ∈ I × Z -: W j→i g j (-s) > 0} and A - i = {(j, s) ∈ I × Z -: W j→i g j (-s) < 0}
, and define the maximal excitatory (respectively inhibitory) strength by

Σ + i = (j,s)∈A + i |W j→i |g j (-s) and Σ - i = (j,s)∈A - i |W j→i |g j (-s).
We also assume that

(4.8) 0 ≤ ν i -Σ - i and ν i + Σ + i ≤ 1.
Under these assumptions, one can check that the transition probabilities (4.7) also satisfy Assumption 2. Specifically, we can use (4.9)

               λ i (∅) = 1 -(Σ + i + Σ - i ) which is ≥ 0 since 0 ≤ Σ + i + Σ - i ≤ 1, p ∅ i = ν i -Σ - i λ i (∅) which is ≤ 1 since ν i + Σ + i ≤ 1, λ i ({(j, s)} ↓i ) = |W j→i |g j (-s)
for all (j, s)

∈ A + i ∪ A - i , p {(j,s)} ↓i i (x) = x j,s 1 x i,s:-1 =0 for all (j, s) ∈ A + i , p {(j,s)} ↓i i (x) = (1 -x j,s )1 x i,s:-1 =0 for all (j, s) ∈ A - i ,
where {(j, s)} ↓i = {(j, s), (i, s), . . . , (i, -1)} is the augmentation of the set {(j, s)} on the coordinate i for each (j, s) ∈ A + i ∪ A - i . Hence, the random neighborhoods V ∈ V have cardinality either 0 (when V = ∅) or s + 1 (when V = {(j, s)} ↓i with j = i) or s (when

V = {(i, s)} ↓i ).
Non-linear spike rate functions. In the previous work of [START_REF] Galves | Infinite Systems of Interacting Chains with Memory of Variable Length-A Stochastic Model for Biological Neural Nets[END_REF], the space-time decomposition is restricted to growing sequences of neighborhoods v that are indexed by their range in time. For each i ∈ I, one assumes that there exists a growing sequence J i (1) = {i}, J i ( ) ⊂ J i ( +1) of subsets of I that corresponds to the space positions that are needed when looking at a past of length , so that we can form v i ( ) = J i ( ) × , defining a growing sequence of subsets of I × Z -.

Next let us introduce the following quantities:

α i ( ) = inf x∈{0,1} I×Z -    inf y∈{0,1} I×Z -:y v i ( ) = x p i (y) + inf y∈{0,1} I×Z -:y v i ( ) = x q i (y)    and λ i (v i ( )) = α i ( ) -α i ( -1)
, where for each i ∈ I, q i (y) = 1 -p i (y) and

λ i (∅) = α i (0) = inf x∈{0,1} I×Z -p i (x) + inf x∈{0,1} I×Z -q i (x).
Let us assume that (4.10) sup

i∈I j∈I |W j→i | < ∞, ∈Z + sup i∈I g i ( ) < ∞ and sup i∈I |ϕ i (u) -ϕ i (v)| ≤ γ|u -v|,
where γ is a positive constant.

It has been proved in [START_REF] Galves | Infinite Systems of Interacting Chains with Memory of Variable Length-A Stochastic Model for Biological Neural Nets[END_REF] (see Proposition 2) that the transition probabilities {p i (x), x ∈ {0, 1} I×Z -} admit the following space-time decomposition:

(4.11) p i (x) = λ i (∅)p ∅ i + ∈Z + λ i (v i ( ))p v i ( ) i (x), λ i (∅) + +∞ =1 λ i (v i ( )) = 1, with, p ∅ i ∈ [0, 1] and for ≥ 1, p v i ( ) i (x) is a [0, 1]-valued measurable function which is cylindrical in v i ( ).
Hence, the transition probabilities p i 's also satisfy Assumption 2 in the nonlinear case. The random neighborhoods V ∈ V have cardinality either 0 (when

V = ∅) or |J i ( )| (when V = v i ( )).
Note that in the non-linear case the neighborhoods v i ( ) are dense in time by construction, whereas in the linear case one can obtain a stronger probabilistic sparsity.

Main properties.

Before being able to assess a value to X i,t at site (i, t) for fixed neuron i and time t, we need to understand on which previous sites this value depends. To do so, we use the distribution λ i to obtain a space-time neighborhood of (i, t). More precisely, because the distribution λ i gives a neighborhood for neuron i at time 0, we need to shift it at time t to obtain a realization of the random neighborhood for neuron i at time t by stationarity. Hence if for every t ∈ Z and subset A of I × Z,

A →t = {(j, s + t) for (j, s) ∈ A},
with the convention that ∅ →t = ∅, we can define the random neighborhood K i,t of site (i, t) as

K i,t = V →t i,t
where V i,t is drawn independently of anything else according to λ i . We can proceed independently for all sites (j, s) and obtain K j,s = V →s j,s . By looking recursively at the neighborhoods of the neighborhoods, we are building a whole genealogy in space and time of the site (i, t), that is the list of sites that are really impacting the value X i,t . This genealogy is random and depends only on the realizations of the neighborhoods, i.e. only on the distributions λ i 's.

The study of this space-time genealogy is of utmost importance. Indeed if the genealogy is almost surely finite then we are able to follow classical constructions as done by [START_REF] Galves | Infinite Systems of Interacting Chains with Memory of Variable Length-A Stochastic Model for Biological Neural Nets[END_REF] to write a perfect simulation algorithm. Moreover the study of the length of the genealogy enables us to cut time into almost independent blocks and therefore to have access to concentration inequalities, this second construction being inspired by Viennet (1997), [START_REF] Reynaud-Bouret | Some non asymptotic tail estimates for Hawkes processes[END_REF] or [START_REF] Hansen | Lasso and probabilistic inequalities for multivariate point processes[END_REF]. 4.3.1. Sufficient condition for finite genealogies. For all sites (i, t), let us define recursively A 1 i,t = K i,t and for n ≥ 1,

A n+1 i,t = (∪ (j,s)∈A n i,t K j,s ) \ {A 1 i,t ∪ . . . ∪ A n i,t },
the genealogy stopped after n + 1 generations. The complete genealogy is

G i,t = ∪ ∞ n=1 A n i,t . It is finite if and only if N i,t = inf{n ≥ 1 : A n i,t = ∅},
is finite. This is a consequence of the following property.

Assumption 5. For each i ∈ I, we assume that the mean size of the random neighborhood on neuron i Probabilistic sparsity corresponds here to the fact that the mean size of the random neighborhoods are strictly less than 1.

Thanks to this assumption, we can prove the following result.

Proposition 1. For each i ∈ I, t ∈ Z and ∈ Z + ,

P (N i,t > ) ≤ ( m) .
In particular, under Assumption 5, for all i ∈ I and t ∈ Z,

(4.14) P(N i,t < ∞) = 1,
that is all genealogies are finite almost surely.

4.3.2. Perfect Simulation Algorithm. Fix a site (i, t) and suppose we want to simulate X i,t .

Under Assumption 5, we know the genealogy is finite almost surely and it is possible to build this genealogy recursively without having to generate all the V j,s . Once the genealogy is obtained by going backward in time, it is then sufficient to go forward and simulate the X j,s 's in the genealogy according to the transitions p V j,s (X K j,s ).

More formally, we can use two independent fields of independent uniform random variables on [0, 1], U 1 = (U 1 i,t ) i∈I,t∈Z and U 2 = (U 2 i,t ) i∈I,t∈Z , such that the whole randomness of the construction is encompassed in the field U 1 for the genealogies and in the field U 2 for the forward transitions and such that conditionally on these two fields, the whole simulation algorithm is deterministic. But in practice, we generate U 1 j,s and U 2 j,s only if we need it. This leads to the following algorithm

Step 1. Generate U 1 i,t random uniform variable on [0, 1]. Since V is countable, one can order its elements such that V = {v 1 , ..., v n , ...}. Define the c.d.f. of λ i by F i (0) = λ i (∅) and for n ≥ 1,

F i (n) = λ i (∅) + n k=1 λ i (V k )
and pick the random neighborhood of (i, t) as

K i,t = V →t i,t with V i,t = ∅, if U 1 i,t ≤ F i (0), v n , if F i (n -1) < U 1 i,t ≤ F i (n) for some n ≥ 1 . Initialize A 1 i,t ← K i,t .
Step 2. Generate recursively U 1 j,s for j, s ∈ A n i,t , compute the corresponding V j,s and K j,s as in Step 1 and actualize A n+1 i,t ← ∪ j,s∈A n i,t K j,s \ {A 1 i,t ∪ . . . ∪ A n i,t }. After a finite number of steps, A n i,t is empty and [Step 2.] stops. Let N i,t be the final n of this recursive procedure and the genealogy of (i, t) is given by G

i,t = ∪ N i,t n=1 A n i,t . Step 3. Note that the (j, s)'s in A N i,t -1 i,t
have therefore an empty neighborhood. Generate i.i.d. uniform variables U 2 j,s for (j, s) in

A N i,t -1 i,t
and define (4.15)

X j,s = 1{U 2 j,s ≤ p ∅ j }.
Step 4. Recursively generate U 2 j,s for (j, s) in A i,t recursively from = N i,t -2 to ell = 1 and define (4.16)

X j,s = 1{U 2 j,s ≤ p V j,s j (X K j,s )},
In particular arrived at = 1, one generates (4.17)

X i,t = 1{U 2 i,t ≤ p V i,t j (X K i,t )}.
It is well-known that the algorithm above not only shows the existence but also the uniqueness of the stochastic chain X compatible with Assumptions 1, 2 and 5 (see for instance [START_REF] Galves | Infinite Systems of Interacting Chains with Memory of Variable Length-A Stochastic Model for Biological Neural Nets[END_REF] for formal statement of this result in a close setup).

Note that when simulating the linear Hawkes process, the algorithm reduces to a random walk in the past to find the genealogy, a random decision on the state X j,s at the end of the random walk and a forward decision of the other states X j,s which is then completely deterministic and just depends on the sign of h j→i (-s). 4.3.3. Time length of a genealogy. We are now interested by the time length of a genealogy. Let, for each non-empty subset A of I × Z, T(A) = min{s ∈ Z : (j, s) ∈ A}.

We are interested by the variable T i,t which is equal to t -T(A i,t ) if the genealogy G i,t is non empty and equal to 0 if G i,t is empty. By stationarity its distribution does not depend on t and the behavior of this variable is of course linked to the one of the variables T (V j ) = -T(V j ) for V j obeying the distribution λ j , with the convention that T (∅) = 0. We are interested by conditions under which the variable T i,t has a Laplace transform, that is when

θ → Ψ i (θ) = E(e θT i,t )
is finite for some positive θ. To do so, we are going to assume Assumption 3 that we recall here: There exists a strictly positive θ such that for all i,

ϕ i (θ) = v∈V |v|e θT (v) λ i (v)
is finite and

(4.18) ϕ(θ) = sup i∈I ϕ i (θ) < 1,
Theorem 2. Under Assumption 3, for all i in I, Ψ i (θ) is finite and

Ψ(θ) = sup i∈I Ψ i (θ) ≤ sup i∈I λ i (∅) 1 -ϕ(θ) .
Note that if ϕ i (θ) is finite for some positive θ, lim θ→0 ϕ i (θ) = mi . Therefore if Assumption 5 is fulfilled, lim θ→0 ϕ i (θ) < 1 and it is possible to find θ > 0 such that ϕ i (θ) < 1 as soon as λ i has a Laplace transform. In this sense, and roughly speaking, Assumption 3 is a more stringent condition of probabilistic sparsity than Assumption 5.

Application on the main examples.

Markov chains. In this case, m = 1 -µ and the condition (4.13) is satisfied as soon as µ < 1. Moreover condition (4.18) reduces to e θ (1 -µ) < 1 and it is always possible to find such a θ > 0 as soon as µ < 1.

Chains of infinite order. The space-time decomposition (4.3) implies that

m = ∞ =1 λ( ).
Thus, the condition (4.13) is satisfied as soon as

∞ =1 λ( ) < 1
and similarly the condition (4.18) is satisfied as soon as

∞ =1 e θ λ( ) < 1.
Hence both can be verified if λ is sufficiently exponentially decreasing. Typically one can have λ( ) = e -λ λ / ! with 0 < λ < 1 (Poisson distribution on the range) or λ( ) = (1-p) p with 1/2 < p ≤ 1 (Geometric distribution on the range).

Discrete-time linear Hawkes processes. According to the space-time decomposition (4.6), it follows that for each i ∈ I, m i = Σ + i + Σ - i . Therefore, the condition (4.13) reduces to

sup i∈I (Σ + i + Σ - i ) = sup i∈I j,s |h j→i (-s)| < 1.
Moreover the condition (4.18) becomes sup i∈I j,s e θs |h j→i (-s)| < 1.

So if for instance we can rewrite h j→i (-s) = w j→i g(-s) for a fixed function g of mean 1, the condition (4.13) reduces to sup i∈I j∈I

|w j→i | < 1,
and the additional condition (4.18) is fulfilled for a small enough θ as soon as g has finite exponential moment.

GL neuron model. In the nonlinear case, it has been proved in Galves and Löcherbach (2013) (cf. inequalities (5.57) and (5.58)) that for each i ∈ I the following estimates hold:

(4.19) λ i (∅) ≤ γ j∈I |W j→i | s≥1 g j (s),
and for ≥ 1, (4.20)

λ i (v i ( )) ≤ γ   j / ∈v i ( ) |W j→i | s≥1 g j (s) + j∈v i ( ) |W j→i s≥ g j (s)   .
Therefore, a sufficient condition (cf. inequality (2.9) of (Galves and Löcherbach, 2013)) for Assumption 5 to hold is

sup i∈I ≥1 |v i ( )|   j / ∈v i ( ) |W j→i | s≥1 g j (s) + j∈v i ( ) |W j→i | s≥ g j (s)   < 1 γ .
In the linear case (i.e. when ϕ i (u) = ν i + u), the condition above reduces to

(4.21) sup i∈I ≥1 |v i ( )|   j / ∈v i ( ) |W j→i | s≥1 g j (s) + j∈v i ( ) |W j→i | s≥ g j (s)   < 1.
Using the decomposition (4.9), one can verify that the condition (4.13) is, in the linear case, equivalent to Note that condition (4.21) is usually much stronger than condition (4.22) and that a sparse space-time decomposition of the process allows us to derive existence of the linear process on a larger set of possible choices for w j→i and g j . Once again condition (4.18) is fulfilled under a very similar expression

sup i∈I ≥1 e θ   |W i→i |g i ( ) + j =i,j∈I ( + 1)|W j→i |g j ( )   < 1,
this can be easily fulfilled if g j ( ) = g( ) is exponentially decreasing with ∞ =1 ( +1)g( ) = 1. Indeed (4.22) is implied as in the Hawkes case by sup i∈I j∈I

|W j→i | < 1
and it is easy to find by continuity a small θ > 0 such that (4.18) is fulfilled too.

Concentration.

4.4.1. Block construction. Thanks to the control of the time length genealogy it is possible to cut the observations X F,-(m-1):T into (overlapping) blocks that form with high probability two families of independent variables. This is a key tool to derive concentration inequalities. This construction is inspired by Viennet (1997), who used as a central element, Berbee's lemma, which is replaced here by Theorem 2. Note that similar coupling arguments have been used in continuous and more restrictive settings (see [START_REF] Reynaud-Bouret | Some non asymptotic tail estimates for Hawkes processes[END_REF]; [START_REF] Hansen | Lasso and probabilistic inequalities for multivariate point processes[END_REF] for linear Hawkes processes, [START_REF] Chen | The Multivariate Hawkes Process in High Dimensions: Beyond Mutual Excitation[END_REF] for bounded Hawkes process and mixing arguments).

Lemma 1. Let m ∈ Z + and F ⊂ I be a finite subset of the neurons, observed on -(m -1) : T . Let B, the grid size, be an integer such that m ≤ B ≤ T /2 and define k = T 2B . Let the 2k + 1 blocks be defined by, for 1 ≤ n ≤ 2k,

I n = {(n -1)B + 1 -m, . . . nB} and I 2k+1 = {2kB + 1 -m, . . . T }.
There exist on a common probability space some stochastic chains X, X 1 ,...,X 2k+1 satisfying the following properties:

1. All the chains X n = (X n i,t ) i∈I,t∈Z have the same distribution as X which satisfies Assumptions 1, 2 and 3 for a given θ, that is a sparse enough space-time decomposition with weights (λ i ) i∈I and transitions (p v i ) i∈I,v∈V . 2. The odd chains X 1 , X 3 , ..., X 2k+1 are independent. 3. The even chains X 2 , ..., X 2k are independent. 4. There exists an event, Ω good , such that on Ω good , X F,In = X n F,In for all n = 1, ..., 2k+1 and such that the probability of Ω c good , under the notation of Theorem 2, is at most

(4.23) |F | (2k + 1) Ψ(θ) (1 -e -θ )
e -θ(B+1-m) .

In particular, by choosing B = m + θ -1 (2 log(T ) + log(|F |)), we obtain that there exists a positive c (θ) such that the probability of Ω c good is at most c (θ)T -1 .

4.4.2. Applications. As an application of Lemma 1, we can derive the following Hoeffding type concentration inequality.

Theorem 3. Let X = (X i,t ) i∈I,t∈Z be a stationary sparse space-time process satisfying Assumptions 1, 2 and 3 for a given θ. For F ⊂ I finite, m ∈ Z + , let f be a real-valued function of X F,t-m:t-1 bounded by M . Let T ∈ Z + such that

m + θ -1 (2 log(T ) + log(|F |)) ≤ T /2 and (4.24) Z(f ) = 1 T T t=1 (f (X F,t-m:t-1 ) -E [f (X F,t-m:t-1 )]) .
Then there exists nonnegative constant c , c", which only depends on θ such that, for any x > 0, (4.25)

P Z(f ) > c"(θ)M 2 m + log T + log |F | T x ≤ c (θ) T + 2e -x .
If there is a finite family F of such f , we also have that

P ∃f ∈ F, Z(f ) > c"(θ)M 2 m + log T + log |F | T x ≤ c (θ) T + 2|F|e -x .
There is a matrix counterpart to the previous inequality, which is an application of now classical results on random matrices (see [START_REF] Tropp | User-Friendly Tail Bounds for Sums of Random Matrices[END_REF] and the references therein).

Theorem 4. Let X = (X i,t ) i∈I,t∈Z be a stationary sparse space-time process satisfying Assumptions 1, 2 and 3 for a given θ. For F ⊂ I finite, m ∈ Z + , let F be a finite family of bounded real-valued functions of X F,t-m:t-1 and denote

M = max{ f g ∞ : f, g ∈ F}. Let T ∈ Z + such that m + θ -1 (2 log(T ) + log(|F |)) ≤ T /2
and define the random matrix Z = (Z(f, g)) f,g∈F where for each f, g ∈ F,

(4.26) Z(f, g) = 1 T T t=1 (f (X F,t-m:t-1 )g(X F,t-m:t-1 ) -E [f (X F,t-m:t-1 )g(X F,t-m:t-1 )]) .
Then there exists nonnegative constant c , c", which only depends on θ such that, for any x > 0, (4.27)

P Z > c"(θ)M 4 |F| 2 m + log T + log |F | T x ≤ c (θ) T + 4|F|e -x ,
where Z corresponds to the spectral norm, that is the largest eigenvalue of the self-adjoint matrix Z.

Back to the Gram matrices.

To control the Gram matrix we need also Assumption 4 that we recall here: There exists some positive µ such that for all i ∈ I, for all x, µ ≤ p i (x) ≤ 1 -µ,

Note that in each of the examples (Markov chain, Hawkes, etc), this assumption is easily fulfilled. For instance in the Hawkes case, this adds the condition µ

≤ ν i -Σ - i ≤ ν i + Σ + i ≤ (1 -µ).
This assumption is useful to bound expectation by changing the underlying measure.

Lemma 2. Under Assumptions 1 and 4, for all non negative function f cylindrical on a fixed finite space-time neighborhood v,

(2(1 -µ)) |v| E ⊗V B(1/2) [f (X v )] ≥ E [f (X v )] ≥ (2µ) |v| E ⊗V B(1/2) [f (X v )]
,

where E ⊗V B(1/2) means that the expectation is taken with respect to the measure where all X i,t 's are i.i.d Bernoulli with parameter 1/2. 5.1. Inv(κ) property for general dictionaries. In this section we prove that the Inv(κ) property holds on an event with high probability for the examples of dictionaries considered in Subsection 3.1. As a by product, we are able to derive oracle inequalities with high probability for these dictionaries. We start with the following result.

Theorem 5. For a finite F ⊂ I and integer T > m ≥ 1, let X F,-(m-1):T be a sample produced by the stationary sparse space-time process X = (X i,t ) i∈I,t∈Z satisfying Assumptions 1, 2 and 3 . Let Φ denote a finite dictionary of bounded functions cylindrical in F ×m and G be the corresponding Gram matrix defined in (3.2). If the matrix E(G) satisfies property Inv(κ ) for some positive constant κ , then for any δ > 0 and T sufficiently large, the Gram matrix G satisfies the property Inv(κ) on an event of probability larger than 1-c T -δ with

κ = κ -c 1 |Φ| Φ 2 ∞ (m + log(T ) + log |F |)(log |Φ| + log δ -1 ) T ,
where c and c 1 are positive constants which only depends on the underlying distribution of X.

To apply Theorem 5 to the dictionaries considered in Section 3.1 we must find the corresponding κ . This is done below.

Short memory effect. To apply Theorem 5 we need first to find κ for this class of models. This is done as follows. Let Q = B(1/2) ⊗V be the probability measure under which all X i,t 's are i.i.d. Bernoulli with parameter 1/2 and denote p j = Q(ϕ j (X -∞:-1 ) = 1) for j ∈ F.

Clearly, p j = 1 -(1/2) m for all j ∈ F and we write p to denote this common value. With this notation, one can check that,

E ⊗V B(1/2) (G) =     p p 2 p 2 ... p 2 p 2 p p 2 ... p 2 ... p 2 p 2 p 2 ... p     .
Such a matrix has only two eigenvalues, namely, p + (|F | -1)p 2 of multiplicity 1 and

p -p 2 = (1/2) m (1 -(1/2) m ) with multiplicity |F | -1. Indeed, ξ is an eigenvalue E ⊗V B(1/2) (G) if and only if there exists a non-null vector u ∈ R F such that (p -p 2 )u + p 2 i u i 1 = ξu.
On the one hand, by choosing the vector u = 0 such that i u i = 0 gives that η = p -p 2 is an eigenvalue with multiplicity |F | -1. On the other hand, the choice i u i = 1 forces that (p -p 2 )u i + p 2 = ξu i for all i ∈ F , ensuring that ξ = p + p 2 (|F | -1) is the second eigenvalue. Its multiplicity is necessarily 1.

Note that if m is large, the smallest eigenvalue of E ⊗V B(1/2) (G) is really small. This can be interpreted in the following way : when m is large, one will find a "1" on every observed neuron in the past, therefore all the ϕ j 's will be equal with high probability and one cannot infer a dependence graph with this dictionary anymore.

Thus, Lemma 2 implies that eigenvalue of E(G) can be lower bounded by

(5.1) κ = (2µ) m|F | (1/2) m (1 -(1/2) m ).
Choosing for a fixed integer η

(5.2) m = η and |F | ≤ log log T,
gives κ of the order (log(T )) -c 3 for some constant c 3 > 0 depending on µ and η.

Cumulative effect. Let α denote the common value of E ⊗V B(1/2) (ϕ 2 j, (X -∞:-1 )) with j ∈ F and 1 ≤ ≤ L, and β be the corresponding value of E ⊗V B(1/2) (ϕ j, (X -∞:-1 )(ϕ k,n (X -∞:-1 )) with j, k ∈ F and k = j and 1 ≤ n, ≤ L. With this notation, one can verify that

α = η 2 + η(η -1) 4 = η 4 + η 2 4 , β = η 2 4 and E ⊗V B(1/2) (G) =     α β β ... β β α β ... β ... β β ... β α     .
Hence, the smallest eigenvalue of

E ⊗V B(1/2) (G) is α -β = η
4 which grows with η = m K . This seems also reasonable since once looking for cumulative effects, the larger the bin size η, the more points you see in it and the more diverse the situations are (hence the dictionary has many different functions) whereas if η is small there is a large probability to see all ϕ j, 's null.

Thus, Lemma 2 implies that eigenvalue of E(G) can be lower bounded by

κ = η 4 (2µ) ηK|F | .
Choosing for some fixed integer η

(5.3) m = ηK with K ≤ log log T and |F | ≤ log log T,
gives κ of the order (log(T )) -c 3 for some other constant c 3 > 0 depending on µ and η.

Cumulative effect with spontaneous apparition. With the same notation of the previous example, one can show that

E ⊗V B(1/2) (G) =     1 η/2 η/2 ... η/2 η/2 α β ... β ... η/2 β ... β α     .
Reasoning by block with the vector (µ, a) with µ ∈ R and a ∈ R K|F | , we end up with (µ, a)

E ⊗V B(1/2) (G)(µ, a) =   µ + η 2 j∈F,k=1,...,K a j,k   2 + η 4 a 2 2 .
But for all 0 < θ < 1,

µ + η 2 a j,k 2 + η 4 a 2 2 ≥ (1 -θ)µ 2 + 1 - 1 θ η 2 4   j∈F,k=1,...,K a j,k   2 + η 4 a 2 2 ≥ (1 -θ)µ 2 - 1 -θ θ K|F |η 2 4 a 2 2 + η 4 a 2 2
By choosing θ = 2ηK|F | 1+2ηK|F | we conclude, thanks to Lemma 2, that the smallest eigenvalue of E(G) can be lower bounded by

κ = (2µ) ηK|F | min 1 1 + 2ηK|F | , η 8
.

Once again choosing for some fixed integer η

(5.4) m = ηK with K ≤ log log T and |F | ≤ log log T, gives κ roughly larger than (log(T )) -c 3 for some other constant c 3 > 0 depending on µ and η.

Next, as a by product of Theorem 5 and Theorem 1, one can derive oracle inequalities for dictionaries above.

Corollary 1. Let Φ be one of the dictionaries presented in Section 3.1, with the choices (5.2), (5.3) or (5.4). Assume one observes X F,-(m-1):T , where the underlying process X satisfies Assumptions 1, 2, 3 and 4.

With the notation of Theorem 1, for T large enough, on an event with probability 1-c 1 /T , the following oracle inequality holds

f -p i (•) 2 T ≤ inf a∈R Φ f a -p i (•) 2 T + c 2 |S(a)| (log(T )) c 3 T ,
where the constant c 1 > 0 depends only on the underlying distribution of X, c 2 > 0 depends on η and γ and constant c 3 > 0 depends on both the underlying distribution of X and η.

Note that the main improvement with respect to [START_REF] Hansen | Lasso and probabilistic inequalities for multivariate point processes[END_REF], is that in all the examples , the constant κ is roughly of order (log(T )) -c 3 , that is asymptotically decreasing in roughly speaking the number of neurons used in the dictionary and not the total number of neurons in the network. This number of neurons that are used, which is bounded by the number of observed neurons, can very slowly grow with T . 5.2. Hawkes dictionary without spontaneous part. In this case the ϕ(X F,-m:-1 )'s are just the X j,s for j ∈ F and s ∈ m and one can prove the following result.

Theorem 6. For a finite F ⊂ I and integer T > m ≥ 1, let X F,-(m-1):T be a sample produced by the stationary sparse space-time process X = (X i,t ) i∈I,t∈Z satisfying Assumptions 1, 2, 3 and 4. For the Hawkes dictionary without spontaneous part, i.e. ϕ = ϕ j,s with ϕ j,s (X F,-m:-1 ) = X j,s for j ∈ F and s ∈ m, the corresponding Gram matrix G defined by (3.2) satisfies for all c > 0, s ≤ m|F | and T large enough, the property RE(κ, c, s) on an event of probability larger than 1

-c T -δ with κ = µ -µ 2 -((1 -2µ) + R T )(1 + c)s, where R T = c 1 T 1/2 (m + log T + log |F |) 1/2 (log m + log |F | + log δ -1 ) 1/2
, for some positive constant c and c 1 which only depends on the underlying distribution of X.

The major point to note is that asymptotically, for slowly growing m and |F | as functions of T , the constant κ does not depend at all on the number of observed neurons and therefore the rate of convergence in Theorem 1 is not worsened by a huge number of observed neurons, |F |. This is a drastic improvement with respect to the previous result of [START_REF] Hansen | Lasso and probabilistic inequalities for multivariate point processes[END_REF] which depends on the total number of neurons in the network. For each fixed c and s, we only need here µ to be close enough to 1/2 to have κ > 0.

It also means that the size of the dictionary might be growing with T , much more rapidly than before: typically m the delay might grow like log(T ) and the number of observed neurons might grow like T or even more rapidly as long as log |F | = o(T 1/2 ). Therefore if one can reasonably well approximate p i by a sparse combination in space and time for which the precise location is unknown, one might by a growing set of observations find the correct set in space and time.

Conclusion.

It is therefore possible to control the Gram matrix for various dictionaries and this even if the finite number of observed neurons is much smaller than the potentially infinite set of existing neurons. The main assumption on the underlying stochastic structure is the probabilistic sparsity (Assumption 3) which allows us to derive concentration inequalities via coupling.

As an open question, it remains to understand the complete link between a well chosen deterministic sparse approximation of p i and the probabilistic sparsity of the λ i 's typically when both the approximation model and the true underlying model coincide, for instance for Hawkes processes. Another way to phrase this is "can we prove the variable selection property, that is typical of Lasso methods? " i.e. " can we find the set of neurons influencing i ?". If the answer seems likely to be yes if they are all observed, it seems intuitive to think in general that a good set of sites (j, s) for the sparse approximation of p i is a level set of the λ i but the fact that the λ i 's are not unique makes this reasoning not straightforward.

Another open question is the minimax rate in this setting. This would involve speaking about regularity of the space-time decomposition, which is not done yet, since we do not even have for the moment uniqueness of the decomposition.

Proofs.

7.1. Proof of Theorem 1. To prove Theorem 1 we use arguments from [START_REF] Gaïffas | High-dimensional additive hazards models and the Lasso[END_REF]. We will need the following Lemmas.

Lemma 3. Let f = f â where â is defined by (3.3). For any vector a ∈ R Φ , the following inequality holds

(7.1) 2 f -f a , f -p i T + γd|â S c (a) | 1 ≤ γd|â S(a) -a S(a) | 1 + 2(b -b) T (â -a),
where S(a) = {ϕ : a ϕ = 0} and the vectors b, b ∈ R Φ are defined in (3.2) and (3.4) respectively.

Proof. Throughout the proof we write ∂g(p) to denote the subddiferential mapping of a convex function g at the point p. One can show that p is a global minimum of the convex function g if and only if 0 ∈ ∂g(p). Now since â is such that â ∈ arg min

a∈R Φ {a T Ga -2a T b + γd|a| 1 }, it follows that 0 ∈ ∂(â T Gâ -2â T b + γd|â| 1 ) = 2Gâ -2b + γd∂|â| 1 .
Thus, it follows that for some ŵ ∈ ∂|â| 1 , the following equation holds 2Gâ -2b + γd ŵ = 0, which implies then (2Gâ -2b + γd ŵ) T (â -a) = 0, for any a ∈ R Φ .

From the above equation we can deduce that for any vector w ∈ ∂|a| 1 and a ∈ R Φ ,

(7.2) (2Gâ -2 b) T (â -a) + γd( ŵ -w) T (â -a) = -γdw T (â -a) + 2(b -b) T (â -a).
One can easily show by the definition of subdifferentials that ( ŵ -w) T (â -a) ≥ 0, for all ŵ ∈ |â| 1 and w ∈ |a| 1 . Thus, using this fact in equation ( 7.2) together with the fact that (2Gâ -2 b) T (â -a) = 2 f -f a , f -p i T , we derive the following inequality

(7.3) 2 f -f a , f -p i T ≤ -γdw T (â -a) + 2(b -b) T (â -a).
It is well know that ∂|a| 1 = {v : |v| ∞ ≤ 1 and v T a = |a| 1 }.

In other words, v ∈ ∂|a| 1 if and only if v ϕ = sign(a ϕ ) for ϕ ∈ S(a) and v ϕ ∈ [-1, 1] for all ϕ ∈ S c (a). Now, take w = (w ϕ ) ϕ∈Φ ∈ ∂|a| 1 of the following form Lemma 4. Let f = f â where â defined by (3.3) with γ ≥ 2 and a ∈ R Φ . On an event on which

w ϕ = sign(a ϕ ), if ϕ ∈ S(a) sign(â ϕ ), if ϕ ∈ S c
(i) f -f a , f -p i T ≥ 0, (ii) |b ϕ -bϕ | ≤ d for all ϕ ∈ Φ,
the following inequality is satisfied,

(7.4) |â S c (a) | 1 ≤ γ + 2 γ -2 |â S(a) -a S(a) | 1 ,
where S(a) = {ϕ : a ϕ = 0}.

Proof. Suppose that f -f a , f -p i T ≥ 0. In this case, Lemma 3 implies that

γd|â S c (a) | 1 ≤ γd|â S(a) -a S(a) | 1 + 2 ϕ∈S(a) (b ϕ -bϕ )(â ϕ -a ϕ ) + 2 ϕ∈S c (a) (b ϕ -bϕ )â ϕ .
On an event on which |b ϕ -bϕ | ≤ d for all ϕ ∈ Φ, we then have that

γd|â S c (a) | 1 ≤ (γ + 2)d|â S(a) -a S(a) | 1 + 2d|â S c (a) | 1 ,
and the result follows.

To prove the first part of Theorem 1 we proceed as follows. First of all, on the event on which f -f a , f -p i T < 0, there is nothing to be proved, since in this case

f -p i 2 T + f -f a 2 T -f a -p i 2 T = f -f a , f -p i T < 0.
Hence, in what follows, take a = (a ϕ ) ϕ∈Φ such that |S(a)| ≤ s and f -f a , f -p i T ≥ 0. In this case, thanks to Lemma 4, we can use Property RE(κ, c(γ), s) to the vector â -a : âS(a) -a S(a)

2 ≤ κ -1 (â -a) T G(â -a). Now, as in the proof of Lemma 4, we know that on an event on which |b ϕ -bϕ | ≤ d for all ϕ ∈ Φ, the following bound holds:

2|(b -b) T (â -a)| ≤ 2d|(â S(a) -a S(a) )| 1 + 2d|â S c (a) | 1
By using this inequality together with Lemma 3, we conclude that and use the inequality qy -y 2 ≤ q 2 /4, which is valid for any q, y > 0.

(7.5) 2 f -f a , f -p i T + (γ -2)d|â S c (a) | 1 ≤ (γ + 2)d|â S(a) -a S(a) | 1 .
For the second part of the result, to control the fluctuations of b ϕ -bϕ , let us note that b ϕ -bϕ = M T , where (M t ) 1≤t≤T is the martingale defined by

M t = t i=1 ϕ(X -∞:t-1 ) T [X i,t -p i (X -∞:t-1 )] .
We can apply the classical bound of Hoeffding's inequality on each increment of the martingale ∆M t . Note that if ϕ(X -∞:t-1 ) is positive,

- ϕ(X -∞:t-1 ) T p i (X -∞:t-1 ) ≤ ∆M t ≤ ϕ(X -∞:t-1 ) T [1 -p i (X -∞:t-1 )],
and if ϕ(X -∞:t-1 ) is negative,

ϕ(X -∞:t-1 ) T [1 -p i (X -∞:t-1 )] ≤ ∆M t ≤ - ϕ(X -∞:t-1 ) T p i (X -∞:t-1 ).
This leads for every θ > 0 to

E(e θ∆Mt |X -∞:t-1 ) ≤ exp θ 2 ϕ(X -∞:t-1 ) 2 8T 2 ≤ exp θ 2 Φ 2 8T 2 . Therefore E(e θM T ) ≤ exp θ 2 Φ 2 8T .
Hence

P(M T ≥ x) ≤ exp θ 2 Φ 2 ∞ 8T -θx .
By optimizing this in θ and applying the same inequality to -ϕ, we get for all positive u

P M T ≥ u Φ 2 ∞ 2T ≤ e -u and P |b ϕ -bϕ | ≥ u Φ 2 ∞ 2T ≤ 2e -u
Therefore taking u = log |Φ| + log(2δ -1 ) and then applying the union bound we obtain the result.

7.2. Proof of Proposition 1. Since {N (i,t) > } = {|A i,t | ≥ 1}, the Markov inequality implies that

P (N i,t > ) ≤ E |A i,t | .
So let us prove by induction that E |A i,t | ≤ ( m) for all ≥ 1. For = 1, we have

E |A 1 i,t | = E [|V i,t |] = mi ≤ m. Next for > 1, E |A i,t | | A -1 i,t ≤ (j,s)∈A -1 i,t E |V →s j,s | ≤ (j,s)∈C i,t ( -1) mj ≤ |A -1 i,t | m.
To conclude the proof take the overall expectation and use the induction assumption given by E |A -1 i,t | ≤ ( m) -1 .

7.3. Proof of Theorem 2. For any fixed n ≥ 1, for all site (i, t) let

G n i,t = ∪ n m=1 A m i,t
We adopt the convention that if G n i,t = ∅, T(G n i,t ) = t and we consider the variable T n i,t = t -T(G n i,t ) as well as its Laplace transform Ψ n i (θ) = E(e θT n i,t ). Let us prove by induction that Ψ n i (θ) is finite and that (7.6)

Ψ n (θ) = sup i Ψ n i (θ) ≤ λ(1 + ϕ(θ) + ... + ϕ(θ) n-2 )1 n>1 + ϕ(θ) n-1 g(θ),
where λ = sup i∈I λ i (∅) and g(θ) = sup i∈I v∈V e θT (v) λ i (v).

Note that g(θ) is finite as soon as ϕ(θ) is and that 0 ≤ λ ≤ 1.

For n = 1, since for all i, T(G

1 i,t ) = T(A 1 i,t ) = T(K i,t ) = t -T (V i,t ) Ψ 1 i (θ) = E (exp [θT (V i,t )]) = v∈V e θT (v) λ i (v) ≤ g(θ).
Next by induction, let us assume (7.6) at level n for all i and let us prove it at level n + 1. Note that because the G n i,t are computed recursively, we have that when K i,t is not empty,

T(G n+1 i,t ) = min (k,r)∈K i,t T(G n k,r ). Therefore if K i,t = ∅, T n+1 i,t = 0 and E exp θT n+1 i,t | K i,t = 1.
This happens with probability λ j (∅).

If K i,t = ∅, E exp θ t -T(G n+1 i,t ) | K j,t = E exp θ max (k,r)∈K i,t t -T(G n k,r ) | K i,t ≤ (k,r)∈K i,t e θ(t-r) E exp θ r -T(G n k,r ) | K i,t .
Since (see the algorithm) K i,t only depends on U 1 j,t and G n k,r only depends on the U 1 k ,r

for k ∈ I, r ≤ r and r < t, it follows that

T(G n k,r ) is independent of K i,t . Hence if K i,t = ∅ E exp θT n+1 i,t | K j,t ≤ (k,r)∈K i,t e θ(t-r) Ψ n k (θ) ≤   (k,r)∈K i,t e θ(t-r)   Ψ n (θ) ≤ |K i,t |e θ(t-T(K j,t )) Ψ n (θ) ≤ |V i,t |e θT (V i,t ) Ψ n (θ).
We obtain by taking the overall expectation that

Ψ n+1 i (θ) ≤ λ + ϕ(θ)Ψ n (θ),
so that sup i∈I Ψ n+1 i (θ) is finite and (7.6) holds at level n + 1 by induction. To conclude, it is sufficient to remark that by the monotone convergence theorem, Ψ n i (θ) → n→∞ Ψ i (θ) which are therefore upper bounded by λ/(1 -ϕ(θ)). This concludes the proof. 7.4. Proof of Lemma 1. We use the perfect simulation algorithm to construct these chains. Let U 0 = (U 0,1 i,t , U 0,2 i,t ) i∈I,t∈Z , . . . ,

U 2k+1 = (U 2k+1,1 i,t , U 2k+1,2 i,t
) i∈I,t∈Z be independent fields of independent random variables with uniform distribution on [0, 1]. We assume that these sequences are defined in the same probability space and set ( Ω, F, P) to be this common probability space.

The perfect simulation algorithm performed with the same field U 0 on each site (i, t) yields the construction of X = (X i,t ) i∈I,t∈Z .

For any n, the chain X n is also built similarly via the perfect simulation algorithm but with the field U n except on a small portion of time where we use U 0 . More precisely, we use the following variables

(U n,1 i,t , U n,2 i,t ) i∈I,t≤(n-2)B , (U 0,1 i,t , U 0,2 i,t ) i∈I,(n-2)B<t≤nB , (U n,1 i,t , U n,2 i,t ) i∈I,t>nB ,
for 1 ≤ n ≤ 2k and for n = 2k + 1, (U n,1 i,t , U n,2 i,t ) i∈I,t≤(2k-1)B , (U 0,1 i,t , U 0,2 i,t ) i∈I,(2k-1)B<t≤T , (U n,1 i,t , U n,2 i,t ) i∈I,t>T .

Since all chains are simulated with the same set of weights (λ i ) i∈I and transitions (p v i ) i∈I,v∈V , they have obviously the same distribution. Since the algorithms use disjoint sets of uniform variables for the odd (resp. even) chains, they are obviously independent and therefore Items 1-3 follows easily from the construction.

Let G i,t be the genealogy of site (i, t) in the chain X and T i,t = T(G i,t ). For any n, any i ∈ F and any t ∈ I n , if T i,t > (n -2)B, then we use exactly the same set of uniform variables to produce the values of X i,t and X n i,t and their values are equal. Therefore on

Ω good = ∩ i∈F ∩ 2k+1 n=1 ∩ t∈In {T i,t > (n -2)B}, X F,In = X n F,
In for all n = 1, ..., 2k + 1. Note that Ω good only depends on X.

It remains to control P(Ω c good ). By a union bound, and the application of Theorem 2, we obtain

P(Ω c good ) ≤ i∈F 2k+1 n=1 t∈In P(T i,t ≤ (n -2)B) ≤ i∈F 2k+1 n=1 t∈In P(t -T i,t ≥ t -(n -2)B) ≤ i∈F 2k+1 n=1 t∈In e -θ(t-(n-2)B) Ψ(θ) ≤ |F |(2k + 1) e -θ(B-m+1)
1 -e -θ Ψ(θ).

In particular if we choose B = m + θ -1 (2 log(T ) + log(|F |),

P(Ω c good ) ≤ 2k + 1 T 2 Ψ(θ) 1 -e -θ ,
which concludes the proof.

Proof of Theorem 3. Take

B = m + θ -1 (2 log(T ) + log(|F |)), k = T
2B and use the probability space ( Ω, F, P) and the stochastic chains X, . . . , X 2k+1 given by Lemma 1. By Lemma 1-Item 1 we can assume that Z is also defined on ( Ω, F, P). Define also a partition J 1 , . . . , J 2k+1 of 1 : T as follows:

J n = {1 + (n -1)B, . . . , nB} for 1 ≤ n ≤ 2k, and J 2k+1 = {1 + 2kB, . . . , T }. For each 1 ≤ n ≤ 2k + 1, write S n = 1 T t∈Jn f (X n F,t-m:t-1
) and note that S n only depends on the t's in I n as defined in Lemma 1. Since

|J n | ≤ B for all 1 ≤ n ≤ 2k + 1, it holds |S n | ≤ M B/T .
Observe that Lemma 1-Item 1 and 4 ensure that on Ω good , Z = 2k+1 n=1 (S n -E(S n )), so that for any w > 0, we have

P(Z > w) ≤ P(Ω c good ) + P 2k+1 n=1 (S n -E(S n )) > w ≤ c (θ) T + P 2k+1 n=1 (S n -E(S n )) > w .
Moreover, if we denote

Z 1 = k+1 n=1 (S 2n-1 -E(S 2n-1 )) and Z 2 = k n=1 (S 2n -E(S 2n ), then P 2k+1 n=1 (S n -E(S n )) > u + v ≤ P (Z 1 > u) + P (Z 2 > v) ,
for all u + v = w. Lemma 1-Item 3 implies that S 2 , . . . , S 2k are independent, so that by the classical Hoeffding inequality, we have for any x > 0, P Z 1 > kB 2 M 2 T -2 x/2 ≤ e -x , and similarly

for P Z 1 > (k + 1)B 2 M 2 T -2 x/2 ≤ e -x . Hence P Z > kB 2 M 2 T -2 x/2 + (k + 1)B 2 M 2 T -2 x/2 ≤ c (θ) T + 2e -x . But k ≤ T (2B) -1 and k + 1 ≤ (T + 2B)(2B) -1 ≤ T /B.
This leads directly to the first result.

For the second result, note that we can restrict ourselves to Ω good once and for all at the beginning and use the union bound only on the auxiliary independent chains, which explains why we pay |F| only in front of the deviation e -x . 7.6. Proof of Theorem 4. Let ( Ω, F, P) be the probability space and X, . . . , X 2k+1 be the stochastic chains given by Lemma 1. By Lemma 1-Item 1 we can assume that Z is also defined on ( Ω, F, P). We write Ẽ to denote the expectation taken with respect the probability measure P. Now, let B, k, J 1 , . . . , J 2k+1 as in the proof of Theorem 3 and define for 1 ≤ n ≤ 2k + 1, the random matrix Σ n = ((Σ n (f, g)) f,g∈F as follows:

Σ n (f, g) = 1 T t∈Jn f (X n F,t-m:t-1 )g(X n F,t-m:t-1 ) -E(f (X n F,t-m:t-1 )g(X n F,t-m:t-1 ) .

Clearly Ẽ(Σ n ) = 0. To apply Theorem 1.3 of [START_REF] Tropp | User-Friendly Tail Bounds for Sums of Random Matrices[END_REF], we need to find a deterministic self-adjoint matrix A n such that A 2 n -Σ 2 n is non negative. This means that for all vector x ∈ R F ,

x [A 2 n -Σ 2 n ]x ≥ 0.

By taking A n = σI n , it is sufficient to prove that x Σ 2 n x ≤ σ 2 x 2 .

But

x Σ 2 n x = f,g∈F

x f x g 1 T 2

t,t ∈Jn h∈F f (X n F,t-m:t-1 )h(X n F,t-m:t-1 ) -E(f (X n F,t-m:t-1 )h(X n F,t-m:t-1 ) × h(X n F,t -m:t -1 )g(X n F,t -m:t -1 ) -E(h(X n F,t -m:t -1 )g(X

M 4 ≤ 4|F| 2 B 2 M 4 T 2 x 2 .
Hence σ = 2|F |BM 2 T works. Denote Z 1 = k+1 n=1 Σ 2n-1 and Z 2 = k n=1 Σ 2n . Lemma 1 implies that on Ω good , Z = Z 1 + Z 2 , so that by the triangle inequality we have for any u > 0 and v > 0, P( Z > u + v) ≤ P(Ω c good ) + P( Z 1 > u) + P( Z 2 > v).

Since by Lemma 1-item 3, Σ 2 , Σ 4 , . . . , Σ 2k are i.i.d random matrices, we can apply Theorem 1.3 of [START_REF] Tropp | User-Friendly Tail Bounds for Sums of Random Matrices[END_REF] to deduce that for any v > 0,

P Z 2 > √ 8kσ 2 v ≤ 2|F|e -v ,
Similarly, we have that for any x > 0, P Z 2 > 8(k + 1)σ 2 u ≤ 2|F|e -u , and as a consequence, it follows that for any x > 0, P Z > √ 8kσ 2 x + 8(k + 1)σ 2 x ≤ c (θ) T + 4|F|e -x .

Since k 1/2 + (k + 1) 1/2 ≤ (4T /B) 1/2 , the result follows from the inequality above.

7.7. Proof of Lemma 2. The proof is done for the lower bound. The argument is similar for the upper bound. We use induction on the time length of v. If v = ∅, f is constant and E(f (X v )) = E ⊗V B(1/2 (f (X v )). Let Q = B(1/2) ⊗v . If the time length of v is strictly positive, let t be the maximal time of v and let w t = {(i, t) for i such that (i, t) ∈ v}.

E(f (X v )) = E[E(f (X v )|X -∞:t-1 )] = E   xw t ∈{0,1} w t
f ((X v\wt , x wt ))P(X wt = x wt |X -∞:t-1 )

  = E   xw t ∈{0,1} w t f ((X v\wt , x wt )) i/(i,t)∈wt P(X i,t = x i,t |X -∞:t-1 )   ≥ (2µ) |wt| E   xw t ∈{0,1} w t f ((X v\wt , x wt ))Q(X i,t = x i,t )  
But xw t ∈{0,1} w t f ((X v\wt ), x wt ))Q(X i,t = x i,t ) is a cylindrical function on v \ w t with time length strictly smaller than v, so by induction,

E(f (X v )) ≥ (2µ) |wt| (2µ) |v\wt| E ⊗V B(1/2)   xw t ∈{0,1} w t f ((X v\wt ), x wt ))Q(X i,t = x i,t )   ≥ (2µ) |v| E ⊗V B(1/2) (f (X v )),
which concludes the proof.

7.8. Proof of Theorem 5. For any a ∈ R Φ such that a = 1, we have by Cauchy-Schwarz inequality (7.7) κ ≤ a E(G)a ≤ a Ga + a (G -E(G))a ≤ a Ga + G -E(G) , so that the result follows from Theorem 4 with x = log(4|F|/δ) and F = Φ.

7.9. Proof of Theorem 6. First of all, remark that thanks to Lemma 2 and since ϕ in this case depends on a neighborhood of size 1, one has that E(G ϕ,ϕ ) = E(ϕ(X) 2 ) ≥ 2µ1/2 = µ and similarly for ϕ = ϕ , ϕϕ is positive and depends on a neighborhood of size 2, hence

(1 -µ) 2 ≥ E(G ϕ,ϕ ) ≥ µ 2 .
Moreover let us apply our version of Hoeffding's inequality, i.e. the second result of Theorem 3 on all the ϕ 2 = ϕ, ϕϕ and -ϕϕ for ϕ = ϕ . Hence there exists and event of probability larger than 1 -c (θ)

T -δ such that for all ϕ, ϕ ,

ϕ = ϕ ∈ Φ a ϕ a ϕ < 0 a ϕ a ϕ -R T |a| 2 1 ≥ (µ -µ 2 ) a 2 + µ 2   ϕ∈Φ a ϕ   2 -((1 -2µ) -R T )|a| 2 1 ≥ (µ -µ 2 ) a 2 -((1 -2µ) + R T ) [|a J | 1 + |a J c | 1 ] 2 ≥ (µ -µ 2 ) a 2 -((1 -2µ) + R T ))(1 + c) 2 |a J | 2 1 ≥ (µ -µ 2 ) a J 2 -((1 -2µ) + R T )(1 + c)s a J 2 ,
which is the desired result.

7.10. Proof of Corollary 1. We shall prove only for the short effect dictionary. The other cases are treated similarly. For this choice of dictionary Φ ∞ = 1 and |Φ| = |F |. Hence, by applying Theorem 5 and Theorem 1 both with δ = T -1 one deduces that, for T large enough, on an event of probability larger then 1-c 1 /T , the following oracle inequality holds with c 1 depending only on the distribution of X and κ given by (5.1). Now, for the choices given by (5.2), (5.3) and (5.4), then, as seen previously κ = c 2 log(T )) -c 3 , for positive constants c 2 and c 3 depending only on m and µ and κ = c 2 (log T ) c 3

(1 -o(1)).

By plugging κ into (7.8), the result follows.

  w T (â -a) = ϕ∈S(a) sign(a ϕ )(â ϕ -a ϕ ) + |â S c (a) | 1 .Thus, by plugging this identify into inequality (7.3), we obtain that2 f -f a , f -p i T + γd|â S c (a) | 1 ≤ -γd ϕ∈S(a) sign(a ϕ )(â ϕ -a ϕ ) + 2(b -b) T (â -a),and the result follows, because | -ϕ∈S(a) sign(a ϕ )(â ϕ -a ϕ )| ≤ |â S(a) -a S(a) | 1 .

Finally

  , by Cauchy-Schwartz inequality, we know that |â S(a) -a S(a) | 1 ≤ S(a) âS(a) -a S(a) ≤ S(a)κ -1 (â -a) T G(â -a).

  |G ϕ,ϕ -E(G ϕ,ϕ )| ≤ R T , with R T = c"(θ) (m + log T + log |F |) T log 4|Φ| 2 δ ,which means that there exists a constant c 1 depending only on the distribution such that for T large enough (depending on θ and |F |)R T = c 1 T -1 (m + log T + log |F |) 1/2 (log m + log |F | + log δ -1 ) 1/2 .Therefore on this event, for all a and J such that |J| ≤ s and |aJ c | 1 ≤ c|a J | 1 , and if µ 2 ≥ R T , a Ga = ϕ∈Φ a 2 ϕ G ϕ,ϕ + ϕ =ϕ ∈Φ a ϕ a ϕ G ϕ,ϕ ≥ (µ -R T ) ϕ∈Φ a 2 ϕ + (µ 2 -R T ) ϕ = ϕ ∈ Φ a ϕ a ϕ ≥ 0 a ϕ a ϕ + ((1 -µ) 2 + R T ) ϕ = ϕ ∈ Φ a ϕ a ϕ < 0 a ϕ a ϕ ≥ (µ -µ 2 ) a 2 + µ 2 ϕ,ϕ ∈Φ a ϕ a ϕ + (1 -2µ)

  p i (•) 2 T + 4κ -1 |S(a)| (log |F | + log(2T )) 2T ,where c 1 depends only on the distribution of X andκ = κ -c 1 T -1/2 |F | 1/2 (m + log(T ) + log |F |) 1/2 (log |F | + log δ -1 ) 1/2 ,

Acknowledgements. This research has been conducted as part of FAPESP project Research, Innovation and Dissemination Center for Neuromathematics (grant 2013/07699-0). This work was also supported by the French government, through the UCA Jedi Investissements dAvenir managed by the National Research Agency (ANR-15-IDEX-01), by the structuring program C@U CA of Université Côte d'Azur and by the interdisciplinary axis MTC-NSC of the University of Nice Sophia-Antipolis. We would like to thank anonymous referees for their helpful comments that improved the manuscript.

Electronic Journal of Statistics 3 1360-1392. Viennet, G. (1997). Inequalities for absolutely regular sequences: application to density estimation. Probability Theory and Related Fields 107 467-492.