# Sparse space-time models: Concentration Inequalities and Lasso

G. Ost<EMAIL_ADDRESS>[ P. Reynaud-
<EMAIL_ADDRESS>[ Universidade Federal do Rio de Janeiro,
Brasil m1 and Université Côte d’Azur, CNRS, LJAD, Francem2

###### Abstract

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.

,

,

,

Restricted eigenvalue,

Chains of infinite order,

Perfect Simulation,

Concentration inequalities,

Oracle inequalities,

Lasso Estimator,

Stochastic neuronal networks,

###### keywords:

[class=MSC]

###### keywords:

and

t1

##  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 Bühlmann (2009); Bühlmann and van de
Geer (2011); 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 Candès and Tao (2005);
Rudelson and Vershynin (2008) or the references in Tropp (2015)).

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 Kock and Callot (2015) where the probabilistic framework is of auto-
regressive kind or Gaïffas and Matulewicz (2019) 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 Kock and Callot (2015); Basu and Michailidis (2015); Jiang, Raskutti
and Willett (2015); Hunt et al. (2018)).

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 Sacerdote and Giraudo
(2013)), 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 Cofré and Cessac (2014); Galves and
Löcherbach (2016)).

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
Pouzat and Chaffiol (2009) on Wold processes, Chen et al. (2017) on Hawkes
processes or Mark, Raskutti and Willett (2018) on Poisson counts). Let us
underline the work by (Hansen, Reynaud-Bouret and Rivoirard, 2015), 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
Kelly et al. (2010) 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 : Lerasle and
Takahashi (2016) and Duarte et al. (2016). In Lerasle and Takahashi (2016),
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 Duarte et
al. (2016), 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
Mark, Raskutti and Willett (2019), 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 Galves and Löcherbach (2013) model and Kalikow-type decompositions
(see Kalikow (1990); Galves et al. (2013)), we consider discrete time models
for which the probability 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 Galves and Löcherbach (2013), 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 ${\mathbb{N}}$ to denote the set of natural numbers
$\\{0,1,2,\ldots\\}$. The sets of integers $\\{\ldots,-1,0,1,\ldots\\}$ is
denoted by ${\mathbb{Z}}$. The set of strictly negative and positive integers
are denoted by ${\mathbb{Z}}_{-}$ and ${\mathbb{Z}}_{+}$ respectively.

We consider a stationary stochastic chain ${\bf X}=(X_{i,t})_{i\in
I,t\in{\mathbb{Z}}}$ taking values in $\\{0,1\\}^{I\times{\mathbb{Z}}}$,
defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, where $I$ is
a countable (possibly infinite) set. The set $I$ represents the set of neurons
in the network. For each $i\in I$ and $t\in{\mathbb{Z}}$,

$X_{i,t}=\begin{cases}1,\ \mbox{if neuron}\ i\ \mbox{spikes at time}\ t,\\\
0,\ \mbox{otherwise}.\end{cases}$

The configuration of ${\bf X}$ at time $t\in{\mathbb{Z}}$ is denoted by
$X_{t}=(X_{i,t},i\in I).$ For $s,t\in{\mathbb{Z}}$ with $s<t$, $X_{i,s:t}$
stands for the collection $(X_{i,s},\ldots,X_{i,t})$ and $X_{s:t}$ for the
collection $(X_{i,r})_{i\in I,s\leq r\leq t}$. For each $t\in{\mathbb{Z}}$,
$X_{-\infty:t}$ denotes the past history $(\ldots,X_{t-1},X_{t})$ of ${\bf X}$
at time $t+1$. Note that the past histories have space-time components. For
$F\subset I$ and $t\in{\mathbb{Z}}$, $X_{F,t}=(X_{i,t},i\in F)$ denotes the
configuration of ${\bf X}$ at time $t$ restricted to set $F$. More generally,
for any subset $v\subset I\times{\mathbb{Z}}$, $X_{v}$ denotes the collection
$(X_{i,t})_{(i,t)\in v}$.

######  Assumption 1.

For each $t\in{\mathbb{Z}}$, given the past history $X_{-\infty:t}$, the
neurons spike independently of each other at time $t+1$, i.e., for any finite
set $J\subset I$ and $(a_{i})_{i\in J}\in\\{0,1\\}^{J},$

${\mathbb{P}}(\cap_{i\in J}\\{X_{i,t+1}=a_{i}\\}|X_{-\infty:t}=x)=\prod_{i\in
J}{\mathbb{P}}(X_{i,t+1}=a_{i}|X_{-\infty:t}=x)\ \ {\mathbb{P}}\mbox{-a.e.}\
x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}.$

Since the stochastic chain ${\bf X}$ is stationary, Assumption 1 implies that
the dynamics of ${\bf X}$ is fully characterized by the transition
probabilities

$p_{i}(x)={\mathbb{P}}(X_{i,0}=1|X_{-\infty:-1}=x),\
x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}},\ i\in I.$

These transition probabilities are all assumed to be measurable functions of
$x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}.$

Hereafter, we need the following notation. For any neighborhood $v\subset
I\times{\mathbb{Z}}_{-}$ and $x,y\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}$, we
write $x\stackrel{{\scriptstyle v}}{{=}}y$ to indicate $y_{v}=x_{v}$. For any
real-valued function $f$ on $\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}$ and subset
$v\subset I\times{\mathbb{Z}}_{-}$, we say $f$ is cylindrical in $v$ and write
$f(x)=f(x_{v})$, if $f(x)=f(y)$ for any
$x,y\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}$ such that
$x\stackrel{{\scriptstyle 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 $\mathcal{V}$ the collection of finite neighborhoods, i.e. finite
subsets of $I\times{\mathbb{Z}}_{-}$ and we consider processes for which the
following decomposition holds.

######  Assumption 2 (Space-time decomposition).

For all $v$ in $\mathcal{V}$ and $i$ in $I$, there exists a $[0,1]$-valued
measurable function $p_{i}^{v}(.)$, cylindrical in $v$, and a non negative
weight $\lambda_{i}(v)$, such that for all
$x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}$ and $i\in I$,

$\left\\{\begin{array}[]{l}p_{i}(x)=\lambda_{i}(\emptyset)p_{i}^{\emptyset}(x)+\sum_{v\in\mathcal{V},v\neq\emptyset}\lambda_{i}(v)p_{i}^{v}(x),\\\
{}\\\ \sum_{v\in\mathcal{V}}\lambda_{i}(v)=1.\\\ \end{array}\right.$

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\in\mathcal{V}$, let
$T(v)=-\min(s\in{\mathbb{Z}}_{-},(j,s)\in v)$ be the corresponding time
length, with the convention that $T(\emptyset)=0$. We also assume the
following.

######  Assumption 3.

There exists a strictly positive $\theta$ such that for all $i$,

$\varphi_{i}(\theta)=\sum_{v\in\mathcal{V}}|v|e^{\theta T(v)}\lambda_{i}(v)$

is finite and

$\varphi(\theta)=\sup_{i\in I}\varphi_{i}(\theta)<1.$ (2.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 $\mu$ such that for all $i\in I$, for all $x$,

$\mu\leq p_{i}(x)\leq 1-\mu,$

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\subset I$, subset of observed neurons, and integers $T>m\geq
1$ measuring the observation window, the aim is to estimate $x\mapsto
p_{i}(x)$ for a fixed neuron $i\in F$, given the sample $X_{F,-(m-1):T}$. To
that end, for each time $1\leq t\leq 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\subset I\times{\mathbb{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 $\Phi$, i.e. a finite set of real-valued
functions on $\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}$ which are cylindrical in
$F\times\underline{m}$ with $\underline{m}=\\{-m,\ldots,-1\\}.$ More
precisely, for each vector
$a=(a_{\varphi})_{\varphi\in\Phi}\in{\mathbb{R}}^{\Phi}$, we denote

$x\mapsto f_{a}(x)=\sum_{\varphi\in\Phi}a_{\varphi}\varphi(x),$ (3.1)

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
$\|\Phi\|_{\infty}$.

We use the least-square contrast defined by

$C(f_{a})=-\frac{2}{T}\sum_{t=1}^{T}f_{a}(X_{F,(t-m):(t-1)})X_{i,t}+\frac{1}{T}\sum_{t=1}^{T}f^{2}_{a}(X_{F,(t-m):(t-1)}),\
a=(a_{\varphi})_{\varphi\in\Phi}\in{\mathbb{R}}^{\Phi}.$

Observe that if for real-valued functions $f$ and $g$ on
$\\{0,1\\}^{I\times{\mathbb{Z}}_{-}},$ we denote $\langle
f,g\rangle_{T}=\frac{1}{T}\sum_{t=0}^{T-1}f(X_{-\infty:t})g(X_{-\infty:t})$
and $\|f\|_{T}$ the corresponding norm, then one has

$C(f_{a})=-2\langle
f_{a},X_{i,\cdot+1}\rangle_{T}+\|f_{a}\|^{2}_{T}=\|f_{a}-X_{i,\cdot+1}\|^{2}_{T}-\|X_{i,\cdot+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 $\varphi,\varphi^{\prime}\in\Phi$ we write,

$b_{\varphi}=\frac{1}{T}\sum_{t=1}^{T}\varphi(X_{F,(t-m):(t-1)})X_{i,t}\quad\mbox{and}\quad\
G_{\varphi,\varphi^{\prime}}=\frac{1}{T}\sum_{t=1}^{T}\varphi(X_{F,(t-m):(t-1)})\varphi^{\prime}(X_{F,(t-m):(t-1)}),$
(3.2)

then $C(f_{a})$ can be rewritten as

$-2a^{\intercal}b+a^{\intercal}Ga,$

where $b=(b_{\varphi},\varphi\in\Phi)$ is a vector of ${\mathbb{R}}^{\Phi}$,
$G=(G_{\varphi,\varphi^{\prime}})_{\varphi,\varphi^{\prime}\in\Phi}$ is the
Gram matrix and $a^{\intercal}$ is the transpose of vector $a$.

In the sequel, let $|a|=(|a_{\varphi}|,\varphi\in\Phi)$,
$|a|_{\infty}=\max_{\varphi\in\Phi}|a_{\varphi}|$,
$\|a\|=\sqrt{a^{\intercal}a}$ and $|a|_{1}={\bf 1}^{\intercal}|a|$ where ${\bf
1}$ is the vector with all coordinates equal to $1$.

Following Hansen, Reynaud-Bouret and Rivoirard (2015), we minimize $C(f_{a})$
subject to a $\ell_{1}$-penalization on the vector
$a=(a_{\varphi},\varphi\in\Phi)$. Precisely, we choose the function
$\hat{f}=f_{\hat{a}}$ where

$\hat{a}\in\arg\min_{a\in{\mathbb{R}}^{\Phi}}\left\\{-2a^{\intercal}b+a^{\intercal}Ga+\gamma
d|a|\right\\},$ (3.3)

for $d$ a positive term controlling the random fluctuations and $\gamma>0$, a
tuning parameter.

The active set $S(a)$ of a vector $a\in{\mathbb{R}}^{\Phi}$ is the set
$S(a)=\\{\varphi:a_{\varphi}\neq 0\\}.$ We shall denote for any subset
$J\subset\Phi$ and any $a\in{\mathbb{R}}^{\Phi}$,
$a_{J}\in{\mathbb{R}}^{\Phi}$ 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 $\varphi\in\Phi,$

$\bar{b}_{\varphi}=\frac{1}{T}\sum_{t=0}^{T-1}\varphi(X_{F,t-m:t})p_{i}(X_{-\infty:t}).$
(3.4)

###  3.1 Examples of dictionaries

Let us present briefly some examples of dictionaries that might be useful.

##### Short memory effect

Let the dictionary $\Phi$ be defined by the set $\\{\varphi_{j}:j\in F\\}$
where

$\varphi_{j}(x)=\begin{cases}1,\ \mbox{if}\ x_{j,s}=1\ \mbox{for some}\ -m\leq
s\leq-1\\\ 0,\ \mbox{otherwise}\end{cases},\
x\in\\{0,1\\}^{I\times{\mathbb{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=\eta L$ is a much larger parameter and cut the past
$\underline{m}$ into $L$ small pieces of length $\eta$, where the effect of
the spikes are different and cumulative. This leads to the dictionary $\Phi$
defined by the set $\\{\varphi_{j,\ell}:j\in F\ \mbox{and}\ 1\leq\ell\leq
L\\}$ where

$\varphi_{j,\ell}(x)=\sum_{s=-\eta\ell}^{-\eta(\ell-1)-1}x_{j,s},\
x\in\\{0,1\\}^{I\times{\mathbb{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

$\varphi_{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 $\eta=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}+\sum_{j\in F}\sum_{-m\leq s\leq-1}a_{j,-s}x_{j,s},\
x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}},$

which is the exact form of a discrete Hawkes process restricted to
$F\times\underline{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$.

###  3.2 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 $\kappa>0$. The matrix $G$ satisfies Property ${\bf Inv}(\kappa)$ if

$\forall a\in{\mathbb{R}}^{\Phi},\quad a^{\intercal}Ga\geq\kappa\|a\|^{2}$

A weaker version is the restricted eigenvalue condition.

######  Definition 2.

Let $c>0$, $\kappa>0$ and $s\in\mathbb{N}$. The matrix $G$ satisfies Property
${\bf RE}(\kappa,c,s)$ if for all subset $J$ such that $|J|\leq s$ and for all
$a\in{\mathbb{R}}^{\Phi}$ such that

$|a_{J^{c}}|_{1}\leq c|a_{J}|_{1},$

the following holds

$a^{\intercal}Ga\geq\kappa\|a_{J}\|^{2}.$

Our first result establish an oracle inequality for the estimator
$\hat{f}=f_{\hat{a}}$ where $\hat{a}$ is defined by (3.3).

######  Theorem 1.

Let $\gamma\geq 2$, $\kappa>0$ and $s\in\mathbb{N}$. On the event on which

  1. (i)

for all $\varphi\in\Phi$, $|b_{\varphi}-\bar{b}_{\varphi}|\leq d$,

  2. (ii)

and $G$ satisfies ${\bf RE}(\kappa,c(\gamma),s)$ with
$c(\gamma)=\frac{\gamma+2}{\gamma-2}$,

the following inequality is satisfied

$\|\hat{f}-p_{i}(\cdot)\|^{2}_{T}\leq\inf_{a\in{\mathbb{R}}^{\Phi}:\
|S(a)|\leq
s}\left\\{\|f_{a}-p_{i}(\cdot)\|^{2}_{T}+\kappa^{-1}|S(a)|d^{2}\frac{(\gamma+2)^{2}}{4}\right\\}.$
(3.5)

Moreover for any $0<\delta<1$, if $d=d_{\delta}$ with

$d_{\delta}=\sqrt{\|\Phi\|^{2}_{\infty}\frac{\log|\Phi|+\log(2\delta^{-1})}{2T}},$

then
${\mathbb{P}}(\exists\varphi\in\Phi:|b_{\varphi}-\bar{b}_{\varphi}|>d)\leq\delta.$

Equation (3.5) is a classical oracle inequality (see for instance Hansen,
Reynaud-Bouret and Rivoirard (2015) or Hunt et al. (2018) for close set-ups).
This result means that the Lasso estimator gives the best $s$-sparse
approximation of $p_{i}$ based on the dictionary $\Phi$ and that the price to
pay is of the order of $\kappa^{-1}sd^{2}$, if we assume that
$\|\Phi\|_{\infty}\leq 1$. With the choice $d=d_{\delta}$, we have therefore a
price of the order of $\kappa^{-1}s\frac{\log|\Phi|+\log(2\delta^{-1})}{T}$.
Note that if we knew that $p_{i}$ can be indeed decomposed on $\Phi$, meaning
that the model is true and that in particular $p_{i}$ only depends on $s$
elements of the dictionary $\Phi$, 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
$\kappa$, to see if (3.5) gives roughly the best possible rate.

Note that if $G$ satisfies ${\bf{Inv}}(\kappa)$ then one can choose $\gamma=2$
and $s=|\Phi|$ in Theorem 1 and (3.5) can be rewritten as

$\|\hat{f}-p_{i}(\cdot)\|^{2}_{T}\leq\inf_{a\in{\mathbb{R}}^{\Phi}}\left\\{\|f_{a}-p_{i}(\cdot)\|^{2}_{T}+4\kappa^{-1}|S(a)|d^{2}\right\\},$

which is a sharper version of the result proved in Hansen, Reynaud-Bouret and
Rivoirard (2015) in continuous time, up to the fact that they used more
general weights which leads to a weighted $\ell_{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 $\ell_{1}$ norm for sake
of simplicity.

Note also that another (very easy) refinement consists in clipping $\hat{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 Mark, Raskutti and Willett (2018) for Poisson
counts or Basu and Michailidis (2015); Gaïffas and Matulewicz (2019) 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 Basu and
Michailidis (2015); Gaïffas and Matulewicz (2019); Hunt et al. (2018) 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
Hansen, Reynaud-Bouret and Rivoirard (2015), 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 $\kappa$ 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 $\kappa$ 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 Hodara and Löcherbach (2016) for promising results in this
direction).

##  4 Space-time decomposition and concentration

###  4.1 Definition

Let us first recall Assumption 2: For all $v$ in $\mathcal{V}$ and $i$ in $I$,
there exists a $[0,1]$-valued measurable function $p_{i}^{v}(.)$, cylindrical
in $v$, and a non negative weight $\lambda_{i}(v)$, such that for all
$x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}$ and $i\in I$,

$\left\\{\begin{array}[]{l}p_{i}(x)=\lambda_{i}(\emptyset)p_{i}^{\emptyset}(x)+\sum_{v\in\mathcal{V},v\neq\emptyset}\lambda_{i}(v)p_{i}^{v}(x),\\\
{}\\\ \sum_{v\in\mathcal{V}}\lambda_{i}(v)=1.\\\ \end{array}\right.$

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\in\mathcal{V}$ according to the distribution
$\lambda_{i}$. Once this neighborhood $V$ is chosen, we decide if a spike of
neuron $i$ occurs with probability $p_{i}^{V}(x_{V})$ that depends only on the
past history restricted to $V$. Note that $p_{i}^{\emptyset}(x)$ does not
depend on $x$ at all, and we denote this value $p_{i}^{\emptyset}$.

Such a space-time decomposition of the transition probabilities
$\\{p_{i}(x),i\in I,x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}\\}$ generalizes
the classical Kalikow decomposition introduced in Kalikow (1990) and further
developed in Comets, Fernandez and Ferrari (2002), Galves et al. (2013) and
Galves and Löcherbach (2013). The main difference consists in not forcing the
nesting of the neighborhoods $v$ that lie in the support of $\lambda_{i}$.
This helps us to exploit the fact that in many cases the distributions
$\lambda_{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)={\mathbb{P}}(X_{i,0}=0|X_{-\infty:-1}=x)=1-p_{i}(x)$
and $q^{v}_{i}(x)=1-p^{v}_{i}(x)$ for all $i\in I$,
$x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}$, we can also write

$q_{i}(x)=\lambda_{i}(\emptyset)q_{i}^{\emptyset}(x)+\sum_{v\in\mathcal{V},v\neq\emptyset}\lambda_{i}(v)q_{i}^{v}(x),$

where for each $v\in\mathcal{V}$, the function $q_{i}^{v}$ is cylindrical in
$v$.

######  Remark 2.

For a given space-time decomposition, one can use Remark 1 to deduce that for
all $i\in I,$

$\inf_{x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}}p_{i}(x)+\inf_{x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}}q_{i}(x)\geq\lambda_{i}(\emptyset).$

More generally, for any $v\in\mathcal{V}$, one can show that

$\inf_{x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}}\left\\{\inf_{y\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}:\
y\ \stackrel{{\scriptstyle v}}{{=}}\
x}p_{i}(y)+\inf_{y\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}:\ y\
\stackrel{{\scriptstyle v}}{{=}}\
x}q_{i}(y)\right\\}\geq\lambda_{i}(\emptyset)+\sum_{w\subseteq
v,w\neq\emptyset}\lambda_{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.

###  4.2 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\in\\{0,1\\}^{{\mathbb{Z}}_{-}},$

$p(x)={\mathbb{P}}(X_{0}=1|X_{-\infty:-1}=x)={\mathbb{P}}(X_{0}=1|X_{-1}=x_{-1}),$

that is, the stochastic chain ${\bf X}=(X_{t})_{t\in\mathbb{Z}}$ is a Markov
chain of order 1 taking values in $\\{0,1\\}$. To shorten notation, let

$p^{1}={\mathbb{P}}(X_{t}=1|X_{t-1}=1),q^{1}=1-p^{1},p^{0}={\mathbb{P}}(X_{t}=1|X_{t-1}=0)\
\mbox{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}\wedge p^{0}$, $q=q^{1}\wedge q^{0}$ and $\mu=p+q$. If
$0<\mu<1$, then one can write

$p(x)=\mu\frac{p}{\mu}+(1-\mu)\left[\frac{p^{1}-p}{1-\mu}x_{-1}+\frac{p^{0}-p}{1-\mu}(1-x_{-1})\right].$

So one can use as space-time decomposition

$\left\\{\begin{array}[]{lcll}\lambda(\emptyset)&=&\mu\\\
p^{\emptyset}&=&\frac{p}{\mu}\\\ \lambda(\\{-1\\})&=&1-\mu\\\
p^{\\{-1\\}}(x)&=&\frac{p^{1}-p}{1-\mu}x_{-1}+\frac{p^{0}-p}{1-\mu}(1-x_{-1})\\\
\end{array}\right..$ (4.1)

Note that the support of $\lambda$ is then reduced to
$\\{\emptyset,\\{-1\\}\\}$. Note also than it is quite straightforward to
extend this to the multidimensional models considered in Mark, Raskutti and
Willett (2019), 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 ${\bf X}$
is described by the transition probability
$\\{p(x),x\in\\{0,1\\}^{{\mathbb{Z}}_{-}}\\}$. Denote for
$\ell\in{\mathbb{Z}}_{+}$, $\underline{\ell}$ the set $\\{-\ell,...,-1\\}$ and

$\beta_{\ell}=\sup_{x\in\\{0,1\\}^{{\mathbb{Z}}_{-}}}\sup_{\begin{array}[]{c}y,z\in\\{0,1\\}^{{\mathbb{Z}}_{-}}\mbox{
s.t.}\\\
y\stackrel{{\scriptstyle\underline{\ell}}}{{=}}z\stackrel{{\scriptstyle\underline{\ell}}}{{=}}x\end{array}}\\{|p(y)-p(z)|\\}.$

If there exist $\ell_{0}\geq 1$ such that $\beta_{\ell}=0$ for all
$\ell\geq\ell_{0}$, then the stochastic chain ${\bf X}$ is called Markov Chain
of Order $\ell_{0}$. Otherwise, ${\bf X}$ is called Chain of Infinite Order.
We refer the reader to Fernandéz, Ferrari and Galves (2001) for a
comprehensive introduction to Chains of Infinite Order.

If $\beta_{\ell}\to 0$ as $\ell\to\infty$, then
$\\{p(x),x\in\\{0,1\\}^{{\mathbb{Z}}_{-}}\\}$ is said to be continuous and the
sequence $(\beta_{\ell})_{\ell\in{\mathbb{Z}}_{+}}$ is called the continuity
rate. Recall that $q(x)=1-p(x)$ for all $x\in\\{0,1\\}^{{\mathbb{Z}}_{-}}$.
One can then compute for $\ell\in{\mathbb{Z}}_{+}$,

$\alpha(\ell)=\inf_{x\in\\{0,1\\}^{{\mathbb{Z}}_{-}}}\left\\{\inf_{y\in\\{0,1\\}^{{\mathbb{Z}}_{-}}\
s.t.\
y\stackrel{{\scriptstyle\underline{\ell}}}{{=}}x}p(y)+\inf_{y\in\\{0,1\\}^{{\mathbb{Z}}_{-}}\
s.t.\ y\stackrel{{\scriptstyle\underline{\ell}}}{{=}}x}q(y)\right\\}.$

This allows us to define the distribution $\lambda$ which has support only on
the $\underline{\ell}$’s and

$\lambda(\underline{\ell})=\alpha(\ell)-\alpha(\ell-1),$ (4.2)

where
$\alpha(0)=\lambda(\emptyset)=\inf_{x\in\\{0,1\\}^{{\mathbb{Z}}_{-}}}p(x)+\inf_{x\in\\{0,1\\}^{{\mathbb{Z}}_{-}}}q(x)$.
One can show that every continuous transition probability
$\\{p(x),x\in\\{0,1\\}^{{\mathbb{Z}}_{-}}\\}$ admits a decomposition of the
form:

$\begin{cases}p(x)=\lambda(\emptyset)p^{\emptyset}+\sum_{\ell\in{\mathbb{Z}}_{+}}\lambda(\underline{\ell})p^{\underline{\ell}}(x)\\\
\lambda(\emptyset)+\sum_{\ell\in{\mathbb{Z}}_{+}}\lambda(\underline{\ell})=1\end{cases}.$
(4.3)

Moreover (4.3) is a space-time decomposition since $p^{\emptyset}\in[0,1]$ and
for each $\ell\in{\mathbb{Z}}_{+},$
$\\{p^{\underline{\ell}}(x),x\in\\{0,1\\}^{{\mathbb{Z}}_{-}}\\}$ is a
transition probability of a Markov chain of order $\ell$.

####  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\in I:$

$\psi_{i}(x)=\nu_{i}+\sum_{s\in{\mathbb{Z}}_{-}}\sum_{j\in I}h_{j\to
i}(-s)x_{j,s},\mbox{ and }\begin{cases}p_{i}(x)=\psi_{i}(x),\ \mbox{ if
}\psi_{i}(x)\in[0,1],\\\ p_{i}(x)=1,\mbox{ if }\psi_{i}(x)>1,\\\ p_{i}(x)=0,\
\mbox{ if }\psi_{i}(x)<0.\\\ \end{cases}$ (4.4)

In this formula, $\nu_{i}\geq 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\to 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\in I$, we write

$A_{i}^{+}=\\{(j,s)\in I\times{\mathbb{Z}}_{-}:h_{j\to i}(-s)>0\\}\mbox{ and
}A_{i}^{-}=\\{(j,s)\in I\times{\mathbb{Z}}_{-}:h_{j\to i}(-s)<0\\},$

and define the maximal excitatory (respectively inhibitory) strength by

$\Sigma_{i}^{+}=\sum_{(j,s)\in A_{i}^{+}}|h_{j\to i}(-s)|\mbox{ and
}\Sigma_{i}^{-}=\sum_{(j,s)\in A_{i}^{-}}|h_{j\to i}(-s)|.$

Let us assume that

$0\leq\nu_{i}-\Sigma_{i}^{-}\quad\mbox{ and }\quad\nu_{i}+\Sigma_{i}^{+}\leq
1,$ (4.5)

which implies in particular that whatever the past configuration
$x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}$, the transition probability
$p_{i}(x)\in[0,1]$ is always equal to $\psi_{i}(x)$. It also implies that
$\Sigma_{i}^{+}+\Sigma_{i}^{-}\in[0,1]$.

Then one can use for the space-time decomposition:

$\left\\{\begin{array}[]{lcll}\lambda_{i}(\emptyset)&=&1-(\Sigma_{i}^{+}+\Sigma_{i}^{-})&\mbox{
which is }\geq 0\mbox{ since }0\leq\Sigma_{i}^{+}+\Sigma_{i}^{-}\leq 1,\\\
p_{i}^{\emptyset}&=&\frac{\nu_{i}-\Sigma_{i}^{-}}{\lambda_{i}(\emptyset)}&\mbox{
which is }\leq 1\mbox{ since }\nu_{i}+\Sigma_{i}^{+}\leq 1,\\\
\lambda_{i}(\\{(j,s)\\})&=&|h_{j\to i}(-s)|&\mbox{ for all }(j,s)\in
A_{i}^{+}\cup A_{i}^{-},\\\ p_{i}^{\\{(j,s)\\}}(x)&=&x_{j,s}&\mbox{ for all
}(j,s)\in A_{i}^{+},\\\ p_{i}^{\\{(j,s)\\}}(x)&=&(1-x_{j,s})&\mbox{ for all
}(j,s)\in A_{i}^{-}.\end{array}\right.$ (4.6)

It is moreover sufficient to assume that $\Sigma_{i}^{+}+\Sigma_{i}^{-}<1$ to
have $\lambda_{i}(\emptyset)>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)\in I\times I$
for which $h_{j\to i}$ is non zero, is complete, the random neighborhoods
$V\in\mathcal{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 $(\int|h_{j\to i}|)_{i,j}$ is smaller than 1 to
ensure stationnarity of the whole multivariate process. Here this matrix can
be reinterpreted as $H=(\sum_{\ell>1}|h_{j\to i}(\ell)|)_{i,j}$. Therefore
(4.5) is different from the usual assumption: it implies in particular that

$\Sigma^{+}+\Sigma^{-}=H\bf{1}\leq\bf{1}\mbox{ coordinate per coordinate}$

where $\Sigma^{+}=(\Sigma_{i}^{+})_{i}$, $\Sigma^{+}=(\Sigma_{i}^{+})_{i}$ and
${\bf 1}$ is the vector of 1’s.

####  4.2.4 GL neuron model

Let $W_{j\to i}\in{\mathbb{R}}$ with $i,j\in I$, be a collection of real
numbers such that $W_{j\to j}=0$ for all $j.$ For each $i\in I$, let
$\varphi_{i}:{\mathbb{R}}\to[0,1]$ be a non-decreasing measurable function and
$g_{i}=(g_{i}(\ell))_{\ell\in{\mathbb{Z}}_{+}}$ be a sequence of strictly
positive real numbers. Here, $W_{j\to i}$ is interpreted as the synaptic
weight of neuron $j$ on neuron $i,$ $\varphi_{i}$ as the spike rate function
of neuron $i$ and $g_{i}$ as the postsynaptic current pulse of neuron i.

For each $x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}$ and $i\in I$, we define
$L^{i}(x)=\sup\\{s\in{\mathbb{Z}}_{-}:x_{i,s}=1\\}.$ The stochastic chain
${\bf X}$ satisfies a GL neuron model if the transition probabilities
$\\{p_{i}(x),i\in I,x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}\\}$ are given by
(see Galves and Löcherbach (2013))

$p_{i}(x)=\begin{cases}\varphi_{i}(0),\mbox{if}\ L^{i}(x)=-1,\\\
\varphi_{i}\left(\sum_{j\in I}W_{j\to
i}\sum_{s=L^{i}(x)+1}^{-1}g_{j}(-s)x_{j,s}\right),\mbox{otherwise}.\end{cases}$
(4.7)

######  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 $\varphi_{i}(u)=\nu_{i}+u$ with $\nu_{i}\geq 0$ for each $i\in I$.
Similarly to Section 4.2.3, let us denote for each $i\in I,$

$A_{i}^{+}=\\{(j,s)\in I\times{\mathbb{Z}}_{-}:W_{j\to i}g_{j}(-s)>0\\}\mbox{
and }A_{i}^{-}=\\{(j,s)\in I\times{\mathbb{Z}}_{-}:W_{j\to i}g_{j}(-s)<0\\},$

and define the maximal excitatory (respectively inhibitory) strength by

$\Sigma_{i}^{+}=\sum_{(j,s)\in A_{i}^{+}}|W_{j\to i}|g_{j}(-s)\mbox{ and
}\Sigma_{i}^{-}=\sum_{(j,s)\in A_{i}^{-}}|W_{j\to i}|g_{j}(-s).$

We also assume that

$0\leq\nu_{i}-\Sigma_{i}^{-}\quad\mbox{ and }\quad\nu_{i}+\Sigma_{i}^{+}\leq
1.$ (4.8)

Under these assumptions, one can check that the transition probabilities (4.7)
also satisfy Assumption 2. Specifically, we can use

$\left\\{\begin{array}[]{lcll}\lambda_{i}(\emptyset)&=&1-(\Sigma_{i}^{+}+\Sigma_{i}^{-})&\mbox{
which is }\geq 0\mbox{ since }0\leq\Sigma_{i}^{+}+\Sigma_{i}^{-}\leq 1,\\\
p_{i}^{\emptyset}&=&\frac{\nu_{i}-\Sigma_{i}^{-}}{\lambda_{i}(\emptyset)}&\mbox{
which is }\leq 1\mbox{ since }\nu_{i}+\Sigma_{i}^{+}\leq 1,\\\
\lambda_{i}(\\{(j,s)\\}^{\downarrow i})&=&|W_{j\to i}|g_{j}(-s)&\mbox{ for all
}(j,s)\in A_{i}^{+}\cup A_{i}^{-},\\\ p_{i}^{\\{(j,s)\\}^{\downarrow
i}}(x)&=&x_{j,s}1_{x_{i,s:-1}=0}&\mbox{ for all }(j,s)\in A_{i}^{+},\\\
p_{i}^{\\{(j,s)\\}^{\downarrow i}}(x)&=&(1-x_{j,s})1_{x_{i,s:-1}=0}&\mbox{ for
all }(j,s)\in A_{i}^{-},\end{array}\right.$ (4.9)

where $\\{(j,s)\\}^{\downarrow i}=\\{(j,s),(i,s),\ldots,(i,-1)\\}$ is the
augmentation of the set $\\{(j,s)\\}$ on the coordinate $i$ for each $(j,s)\in
A_{i}^{+}\cup A_{i}^{-}.$ Hence, the random neighborhoods $V\in\mathcal{V}$
have cardinality either $0$ (when $V=\emptyset$) or $s+1$ (when
$V=\\{(j,s)\\}^{\downarrow i}$ with $j\neq i$) or $s$ (when
$V=\\{(i,s)\\}^{\downarrow i}$ ).

##### Non-linear spike rate functions

In the previous work of Galves and Löcherbach (2013), the space-time
decomposition is restricted to growing sequences of neighborhoods $v$ that are
indexed by their range in time. For each $i\in I$, one assumes that there
exists a growing sequence $J_{i}(1)=\\{i\\},J_{i}(\ell)\subset J_{i}(\ell+1)$
of subsets of $I$ that corresponds to the space positions that are needed when
looking at a past of length $\ell$, so that we can form
$v_{i}(\ell)=J_{i}(\ell)\times\underline{\ell}$, defining a growing sequence
of subsets of $I\times{\mathbb{Z}}_{-}$.

Next let us introduce the following quantities:

$\displaystyle\alpha_{i}(\ell)=\inf_{x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}}\left\\{\inf_{y\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}:y\stackrel{{\scriptstyle
v_{i}(\ell)}}{{=}}x}p_{i}(y)+\inf_{y\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}:y\stackrel{{\scriptstyle
v_{i}(\ell)}}{{=}}x}q_{i}(y)\right\\}$

and $\lambda_{i}(v_{i}(\ell))=\alpha_{i}(\ell)-\alpha_{i}(\ell-1)$, where for
each $i\in I,$ $q_{i}(y)=1-p_{i}(y)$ and
$\lambda_{i}(\emptyset)=\alpha_{i}(0)=\inf_{x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}}p_{i}(x)+\inf_{x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}}q_{i}(x).$

Let us assume that

$\sup_{i\in I}\sum_{j\in I}|W_{j\to i}|<\infty,\
\sum_{\ell\in{\mathbb{Z}}_{+}}\sup_{i\in I}g_{i}(\ell)<\infty\ \mbox{and}\
\sup_{i\in I}|\varphi_{i}(u)-\varphi_{i}(v)|\leq\gamma|u-v|,$ (4.10)

where $\gamma$ is a positive constant.

It has been proved in Galves and Löcherbach (2013) (see Proposition 2) that
the transition probabilities
$\\{p_{i}(x),x\in\\{0,1\\}^{I\times{\mathbb{Z}}_{-}}\\}$ admit the following
space-time decomposition:

$\begin{cases}p_{i}(x)=\lambda_{i}(\emptyset)p^{\emptyset}_{i}+\sum_{\ell\in{\mathbb{Z}}_{+}}\lambda_{i}(v_{i}(\ell))p^{v_{i}(\ell)}_{i}(x),\\\
\lambda_{i}(\emptyset)+\sum_{\ell=1}^{+\infty}\lambda_{i}(v_{i}(\ell))=1,\end{cases}$
(4.11)

with, $p^{\emptyset}_{i}\in[0,1]$ and for $\ell\geq 1$,
$p^{v_{i}(\ell)}_{i}(x)$ is a $[0,1]$-valued measurable function which is
cylindrical in $v_{i}(\ell)$.

Hence, the transition probabilities $p_{i}$’s also satisfy Assumption 2 in the
nonlinear case. The random neighborhoods $V\in\mathcal{V}$ have cardinality
either $0$ (when $V=\emptyset$) or $\ell|J_{i}(\ell)|$ (when $V=v_{i}(\ell)$).
Note that in the non-linear case the neighborhoods $v_{i}(\ell)$ are dense in
time by construction, whereas in the linear case one can obtain a stronger
probabilistic sparsity.

###  4.3 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 $\lambda_{i}$ to obtain a
space-time neighborhood of $(i,t)$. More precisely, because the distribution
$\lambda_{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\in{\mathbb{Z}}$ and
subset $A$ of $I\times{\mathbb{Z}}$,

${A}^{\to t}=\\{(j,s+t)\mbox{ for }(j,s)\in A\\},$

with the convention that $\emptyset^{\to t}=\emptyset,$ we can define the
random neighborhood $K_{i,t}$ of site $(i,t)$ as

$K_{i,t}=V_{i,t}^{\to t}$

where $V_{i,t}$ is drawn independently of anything else according to
$\lambda_{i}$. We can proceed independently for all sites $(j,s)$ and obtain
$K_{j,s}=V_{j,s}^{\to 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 $\lambda_{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 Galves and Löcherbach (2013) 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), Reynaud-Bouret and Roy (2007) or Hansen, Reynaud-Bouret and
Rivoirard (2015).

####  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\geq 1,$

$A^{n+1}_{i,t}=(\cup_{(j,s)\in
A^{n}_{i,t}}K_{j,s})\setminus\\{A^{1}_{i,t}\cup\ldots\cup A^{n}_{i,t}\\},$

the genealogy stopped after $n+1$ generations.

The complete genealogy is $G_{i,t}=\cup_{n=1}^{\infty}A^{n}_{i,t}$. It is
finite if and only if

$N_{i,t}=\inf\\{n\geq 1:A^{n}_{i,t}=\emptyset\\},$

is finite.

This is a consequence of the following property.

######  Assumption 5.

For each $i\in I$, we assume that the mean size of the random neighborhood on
neuron $i$

$\bar{m}_{i}=\sum_{v\in\mathcal{V}}|v|\lambda_{i}(v),$ (4.12)

is finite and that the maximal mean size satisfies

$\bar{m}=\sup_{i\in I}\bar{m}_{i}<1.$ (4.13)

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\in I$, $t\in{\mathbb{Z}}$ and $\ell\in{\mathbb{Z}}_{+},$

${\mathbb{P}}\left(N_{i,t}>\ell\right)\leq(\bar{m})^{\ell}.$

In particular, under Assumption 5, for all $i\in I$ and $t\in{\mathbb{Z}}$,

${\mathbb{P}}(N_{i,t}<\infty)=1,$ (4.14)

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]$, ${\bf U^{1}}=(U^{1}_{i,t})_{i\in I,t\in{\mathbb{Z}}}$
and ${\bf U^{2}}=(U^{2}_{i,t})_{i\in I,t\in{\mathbb{Z}}}$, such that the whole
randomness of the construction is encompassed in the field ${\bf U^{1}}$ for
the genealogies and in the field ${\bf 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 $\mathcal{V}$
is countable, one can order its elements such that
$\mathcal{V}=\\{v_{1},...,v_{n},...\\}$. Define the c.d.f. of $\lambda_{i}$ by
$F_{i}(0)=\lambda_{i}(\emptyset)$ and for $n\geq 1$,

$F_{i}(n)=\lambda_{i}(\emptyset)+\sum_{k=1}^{n}\lambda_{i}(V_{k})$

and pick the random neighborhood of $(i,t)$ as

$K_{i,t}=V_{i,t}^{\to t}\mbox{ with }V_{i,t}=\begin{cases}\emptyset,\
\mbox{if}\ U^{1}_{i,t}\leq F_{i}(0),\\\ v_{n},\ \mbox{if}\
F_{i}(n-1)<U^{1}_{i,t}\leq F_{i}(n)\ \mbox{for some}\ n\geq 1\end{cases}.$

Initialize $A^{1}_{i,t}\leftarrow K_{i,t}$.

  * Step 2.

Generate recursively $U^{1}_{j,s}$ for ${j,s}\in 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}\leftarrow\left(\cup_{{j,s}\in
A^{n}_{i,t}}K_{j,s}\right)\setminus\\{A^{1}_{i,t}\cup\ldots\cup
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}=\cup_{n=1}^{N_{i,t}}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

$X_{j,s}=1\\{U^{2}_{j,s}\leq p^{\emptyset}_{j}\\}.$ (4.15)

  * Step 4.

Recursively generate $U^{2}_{j,s}$ for $(j,s)$ in $A^{\ell}_{i,t}$ recursively
from $\ell=N_{i,t}-2$ to $ell=1$ and define

$X_{j,s}=1\\{U^{2}_{j,s}\leq p^{V_{j,s}}_{j}(X_{K_{j,s}})\\},$ (4.16)

In particular arrived at $\ell=1$, one generates

$X_{i,t}=1\\{U^{2}_{i,t}\leq p^{V_{i,t}}_{j}(X_{K_{i,t}})\\}.$ (4.17)

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 Galves and Löcherbach (2013) 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\to 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\times{\mathbb{Z}}$,

$\mathbb{T}(A)=\min\\{s\in{\mathbb{Z}}:(j,s)\in A\\}.$

We are interested by the variable $T_{i,t}$ which is equal to
$t-\mathbb{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})=-\mathbb{T}(V_{j})$ for $V_{j}$ obeying the distribution
$\lambda_{j}$, with the convention that $T(\emptyset)=0$. We are interested by
conditions under which the variable $T_{i,t}$ has a Laplace transform, that is
when

$\theta\mapsto\Psi_{i}(\theta)={\mathbb{E}}(e^{\theta T_{i,t}})$

is finite for some positive $\theta$. To do so, we are going to assume
Assumption 3 that we recall here: There exists a strictly positive $\theta$
such that for all $i$,

$\varphi_{i}(\theta)=\sum_{v\in\mathcal{V}}|v|e^{\theta T(v)}\lambda_{i}(v)$

is finite and

$\varphi(\theta)=\sup_{i\in I}\varphi_{i}(\theta)<1,$ (4.18)

######  Theorem 2.

Under Assumption 3, for all $i$ in $I$, $\Psi_{i}(\theta)$ is finite and

$\Psi(\theta)=\sup_{i\in I}\Psi_{i}(\theta)\leq\frac{\sup_{i\in
I}\lambda_{i}(\emptyset)}{1-\varphi(\theta)}.$

Note that if $\varphi_{i}(\theta)$ is finite for some positive $\theta$,
$\lim_{\theta\to 0}\varphi_{i}(\theta)=\bar{m_{i}}$. Therefore if Assumption 5
is fulfilled, $\lim_{\theta\to 0}\varphi_{i}(\theta)<1$ and it is possible to
find $\theta>0$ such that $\varphi_{i}(\theta)<1$ as soon as $\lambda_{i}$ has
a Laplace transform. In this sense, and roughly speaking, Assumption 3 is a
more stringent condition of probabilistic sparsity than Assumption 5.

####  4.3.4 Application on the main examples

##### Markov chains

In this case, $\bar{m}=1-\mu$ and the condition (4.13) is satisfied as soon as
$\mu<1$. Moreover condition (4.18) reduces to $e^{\theta}(1-\mu)<1$ and it is
always possible to find such a $\theta>0$ as soon as $\mu<1$.

##### Chains of infinite order

The space-time decomposition (4.3) implies that

$\bar{m}=\sum_{\ell=1}^{\infty}\ell\lambda(\underline{\ell}).$

Thus, the condition (4.13) is satisfied as soon as

$\sum_{\ell=1}^{\infty}\ell\lambda(\underline{\ell})<1$

and similarly the condition (4.18) is satisfied as soon as

$\sum_{\ell=1}^{\infty}\ell e^{\theta\ell}\lambda(\underline{\ell})<1.$

Hence both can be verified if $\lambda$ is sufficiently exponentially
decreasing. Typically one can have
$\lambda(\underline{\ell})=e^{-\lambda}\lambda^{\ell}/\ell!$ with
$0<\lambda<1$ (Poisson distribution on the range) or
$\lambda(\underline{\ell})=(1-p)^{\ell}p$ with $1/2<p\leq 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\in I$,

$m_{i}=\Sigma^{+}_{i}+\Sigma^{-}_{i}.$

Therefore, the condition (4.13) reduces to

$\sup_{i\in I}(\Sigma^{+}_{i}+\Sigma^{-}_{i})=\sup_{i\in I}\sum_{j,s}|h_{j\to
i}(-s)|<1.$

Moreover the condition (4.18) becomes

$\sup_{i\in I}\sum_{j,s}e^{\theta s}|h_{j\to i}(-s)|<1.$

So if for instance we can rewrite $h_{j\to i}(-s)=w_{j\to i}g(-s)$ for a fixed
function $g$ of mean 1, the condition (4.13) reduces to

$\sup_{i\in I}\sum_{j\in I}|w_{j\to i}|<1,$

and the additional condition (4.18) is fulfilled for a small enough $\theta$
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\in I$ the following estimates
hold:

$\lambda_{i}(\emptyset)\leq\gamma\sum_{j\in I}|W_{j\to i}|\sum_{s\geq
1}g_{j}(s),$ (4.19)

and for $\ell\geq 1$,

$\lambda_{i}(v_{i}({\ell}))\leq\gamma\left(\sum_{j\notin
v_{i}({\ell})}|W_{j\to i}|\sum_{s\geq 1}g_{j}(s)+\sum_{j\in
v_{i}({\ell})}|W_{j\to i}|\sum_{s\geq\ell}g_{j}(s)\right).$ (4.20)

Therefore, a sufficient condition (cf. inequality (2.9) of (Galves and
Löcherbach, 2013)) for Assumption 5 to hold is

$\sup_{i\in I}\sum_{\ell\geq 1}\ell|v_{i}({\ell})|\left(\sum_{j\notin
v_{i}({\ell})}|W_{j\to i}|\sum_{s\geq 1}g_{j}(s)+\sum_{j\in
v_{i}({\ell})}|W_{j\to i}|\sum_{s\geq\ell}g_{j}(s)\right)<\frac{1}{\gamma}.$

In the linear case (i.e. when $\varphi_{i}(u)=\nu_{i}+u$), the condition above
reduces to

$\sup_{i\in I}\sum_{\ell\geq 1}\ell|v_{i}({\ell})|\left(\sum_{j\notin
v_{i}({\ell})}|W_{j\to i}|\sum_{s\geq 1}g_{j}(s)+\sum_{j\in
v_{i}({\ell})}|W_{j\to i}|\sum_{s\geq\ell}g_{j}(s)\right)<1.$ (4.21)

Using the decomposition (4.9), one can verify that the condition (4.13) is, in
the linear case, equivalent to

$\sup_{i\in I}\sum_{\ell\geq 1}\left[\ell|W_{i\to i}|g_{i}(\ell)+\sum_{j\neq
i,j\in I}(\ell+1)|W_{j\to i}|g_{j}(\ell)\right]<1.$ (4.22)

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\to i}$ and $g_{j}$. Once again condition (4.18) is fulfilled under a
very similar expression

$\sup_{i\in I}\sum_{\ell\geq 1}e^{\theta\ell}\left[\ell|W_{i\to
i}|g_{i}(\ell)+\sum_{j\neq i,j\in I}(\ell+1)|W_{j\to i}|g_{j}(\ell)\right]<1,$

this can be easily fulfilled if $g_{j}(\ell)=g(\ell)$ is exponentially
decreasing with $\sum_{\ell=1}^{\infty}(\ell+1)g(\ell)=1$. Indeed (4.22) is
implied as in the Hawkes case by

$\sup_{i\in I}\sum_{j\in I}|W_{j\to i}|<1$

and it is easy to find by continuity a small $\theta>0$ such that (4.18) is
fulfilled too.

###  4.4 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 Reynaud-Bouret and Roy (2007);
Hansen, Reynaud-Bouret and Rivoirard (2015) for linear Hawkes processes, Chen
et al. (2017) for bounded Hawkes process and mixing arguments).

######  Lemma 1.

Let $m\in{\mathbb{Z}}_{+}$ and $F\subset I$ be a finite subset of the neurons,
observed on $-(m-1):T$. Let $B$, the grid size, be an integer such that

$m\leq B\leq\lfloor T/2\rfloor$

and define $k=\lfloor\frac{T}{2B}\rfloor$. Let the $2k+1$ blocks be defined
by, for $1\leq n\leq 2k$,

$I_{n}=\\{(n-1)B+1-m,\ldots nB\\}\mbox{ and }I_{2k+1}=\\{2kB+1-m,\ldots T\\}.$

There exist on a common probability space some stochastic chains ${\bf X}$,
${\bf X^{1}}$,…,${\bf X^{2k+1}}$ satisfying the following properties:

  1. 1.

All the chains ${\bf X^{n}}=(X^{n}_{i,t})_{i\in I,t\in{\mathbb{Z}}}$ have the
same distribution as ${\bf X}$ which satisfies Assumptions 1, 2 and 3 for a
given $\theta$, that is a sparse enough space-time decomposition with weights
$(\lambda_{i})_{i\in I}$ and transitions $(p_{i}^{v})_{i\in
I,v\in\mathcal{V}}$.

  2. 2.

The odd chains ${\bf X^{1}},{\bf X^{3}},...,{\bf X^{2k+1}}$ are independent.

  3. 3.

The even chains ${\bf X^{2}},...,{\bf X^{2k}}$ are independent.

  4. 4.

There exists an event, $\Omega_{good}$, such that on $\Omega_{good}$,
$X_{F,I_{n}}=X^{n}_{F,I_{n}}$ for all $n=1,...,2k+1$ and such that the
probability of $\Omega^{c}_{good}$, under the notation of Theorem 2, is at
most

$|F|\left(2k+1\right)\frac{\Psi(\theta)}{(1-e^{-\theta})}e^{-\theta(B+1-m)}.$
(4.23)

In particular, by choosing $B=m+\theta^{-1}(2\log(T)+\log(|F|))$, we obtain
that there exists a positive $c^{\prime}(\theta)$ such that the probability of
$\Omega^{c}_{good}$ is at most $c^{\prime}(\theta)T^{-1}.$

####  4.4.2 Applications

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

######  Theorem 3.

Let ${\bf X}=(X_{i,t})_{i\in I,t\in{\mathbb{Z}}}$ be a stationary sparse
space-time process satisfying Assumptions 1, 2 and 3 for a given $\theta$. For
$F\subset I$ finite, $m\in{\mathbb{Z}}_{+}$, let $f$ be a real-valued function
of $X_{F,t-m:t-1}$ bounded by $M$. Let $T\in{\mathbb{Z}}_{+}$ such that

$m+\theta^{-1}(2\log(T)+\log(|F|))\leq\lfloor T/2\rfloor$

and

$Z(f)=\frac{1}{T}\sum_{t=1}^{T}\left(f(X_{F,t-m:t-1})-{\mathbb{E}}\left[f(X_{F,t-m:t-1})\right]\right).$
(4.24)

Then there exists nonnegative constant $c^{\prime},c"$, which only depends on
$\theta$ such that, for any $x>0,$

${\mathbb{P}}\left(Z(f)>\sqrt{c"(\theta)M^{2}\frac{m+\log
T+\log|F|}{T}x}\right)\leq\frac{c^{\prime}(\theta)}{T}+2e^{-x}.$ (4.25)

If there is a finite family $\mathcal{F}$ of such $f$, we also have that

${\mathbb{P}}\left(\exists
f\in\mathcal{F},Z(f)>\sqrt{c"(\theta)M^{2}\frac{m+\log
T+\log|F|}{T}x}\right)\leq\frac{c^{\prime}(\theta)}{T}+2|\mathcal{F}|e^{-x}.$

There is a matrix counterpart to the previous inequality, which is an
application of now classical results on random matrices (see Tropp (2012) and
the references therein).

######  Theorem 4.

Let ${\bf X}=(X_{i,t})_{i\in I,t\in{\mathbb{Z}}}$ be a stationary sparse
space-time process satisfying Assumptions 1, 2 and 3 for a given $\theta$. For
$F\subset I$ finite, $m\in{\mathbb{Z}}_{+}$, let $\mathcal{F}$ be a finite
family of bounded real-valued functions of $X_{F,t-m:t-1}$ and denote
$M=\max\\{\|fg\|_{\infty}:f,g\in\mathcal{F}\\}$. Let $T\in{\mathbb{Z}}_{+}$
such that

$m+\theta^{-1}(2\log(T)+\log(|F|))\leq\lfloor T/2\rfloor$

and define the random matrix $Z=(Z(f,g))_{f,g\in\mathcal{F}}$ where for each
$f,g\in\mathcal{F}$,

$Z(f,g)=\frac{1}{T}\sum_{t=1}^{T}\left(f(X_{F,t-m:t-1})g(X_{F,t-m:t-1})-{\mathbb{E}}\left[f(X_{F,t-m:t-1})g(X_{F,t-m:t-1})\right]\right).$
(4.26)

Then there exists nonnegative constant $c^{\prime},c"$, which only depends on
$\theta$ such that, for any $x>0,$

${\mathbb{P}}\left(\|Z\|>\sqrt{c"(\theta)M^{4}|\mathcal{F}|^{2}\frac{m+\log
T+\log|F|}{T}x}\right)\leq\frac{c^{\prime}(\theta)}{T}+4|\mathcal{F}|e^{-x},$
(4.27)

where $\|Z\|$ corresponds to the spectral norm, that is the largest eigenvalue
of the self-adjoint matrix $Z$.

##  5 Back to the Gram matrices

To control the Gram matrix we need also Assumption 4 that we recall here:
There exists some positive $\mu$ such that for all $i\in I$, for all $x$,

$\mu\leq p_{i}(x)\leq 1-\mu,$

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
$\mu\leq\nu_{i}-\Sigma_{i}^{-}\leq\nu_{i}+\Sigma_{i}^{+}\leq(1-\mu)$.

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-\mu))^{|v|}{\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}\left[f(X_{v})\right]\geq{\mathbb{E}}\left[f(X_{v})\right]\geq(2\mu)^{|v|}{\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}\left[f(X_{v})\right],$

where ${\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}$ 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($\kappa$) property for general dictionaries

In this section we prove that the Inv($\kappa$) 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\subset I$ and integer $T>m\geq 1$, let $X_{F,-(m-1):T}$ be a
sample produced by the stationary sparse space-time process ${\bf
X}=(X_{i,t})_{i\in I,t\in{\mathbb{Z}}}$ satisfying Assumptions 1, 2 and 3 .
Let $\Phi$ denote a finite dictionary of bounded functions cylindrical in
$F\times\underline{m}$ and $G$ be the corresponding Gram matrix defined in
(3.2). If the matrix ${\mathbb{E}}(G)$ satisfies property
$Inv(\kappa^{\prime})$ for some positive constant $\kappa^{\prime},$ then for
any $\delta>0$ and $T$ sufficiently large, the Gram matrix $G$ satisfies the
property $Inv(\kappa)$ on an event of probability larger than
$1-\frac{c^{\prime}}{T}-\delta$ with

$\kappa=\kappa^{\prime}-c_{1}|\Phi|\|\Phi\|^{2}_{\infty}\sqrt{\frac{(m+\log(T)+\log|F|)(\log|\Phi|+\log\delta^{-1})}{T}},$

where $c^{\prime}$ and $c_{1}$ are positive constants which only depends on
the underlying distribution of ${\bf X}$.

To apply Theorem 5 to the dictionaries considered in Section 3.1 we must find
the corresponding $\kappa^{\prime}$. This is done below.

##### Short memory effect

To apply Theorem 5 we need first to find $\kappa^{\prime}$ for this class of
models. This is done as follows. Let $Q=\mathcal{B}(1/2)^{\otimes\mathcal{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(\varphi_{j}(X_{-\infty:-1})=1)$ for
$j\in F.$ Clearly, $p_{j}=1-(1/2)^{m}$ for all $j\in F$ and we write $p$ to
denote this common value. With this notation, one can check that,

${\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}(G)=\begin{pmatrix}p&p^{2}&p^{2}&...&p^{2}\\\
p^{2}&p&p^{2}&...&p^{2}\\\ &&&...&\\\ p^{2}&p^{2}&p^{2}&...&p\end{pmatrix}.$

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, $\xi$ is an eigenvalue
${\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}(G)$ if and only if there
exists a non-null vector $u\in{\mathbb{R}}^{F}$ such that

$(p-p^{2})u+p^{2}\sum_{i}u_{i}{\bf 1}=\xi u.$

On the one hand, by choosing the vector $u\neq 0$ such that $\sum_{i}u_{i}=0$
gives that $\eta=p-p^{2}$ is an eigenvalue with multiplicity $|F|-1$. On the
other hand, the choice $\sum_{i}u_{i}=1$ forces that $(p-p^{2})u_{i}+p^{2}=\xi
u_{i}$ for all $i\in F$, ensuring that $\xi=p+p^{2}(|F|-1)$ is the second
eigenvalue. Its multiplicity is necessarily $1.$

Note that if $m$ is large, the smallest eigenvalue of
${\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}(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
$\varphi_{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 ${\mathbb{E}}(G)$ can be lower
bounded by

$\kappa^{\prime}=(2\mu)^{m|F|}(1/2)^{m}(1-(1/2)^{m}).$ (5.1)

Choosing for a fixed integer $\eta$

$m=\eta\mbox{ and }|F|\leq\log\log T,$ (5.2)

gives $\kappa^{\prime}$ of the order $(\log(T))^{-c_{3}}$ for some constant
$c_{3}>0$ depending on $\mu$ and $\eta$.

##### Cumulative effect

Let $\alpha$ denote the common value of
${\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}(\varphi^{2}_{j,\ell}(X_{-\infty:-1}))$
with $j\in F$ and $1\leq\ell\leq L$, and $\beta$ be the corresponding value of
${\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}(\varphi_{j,\ell}(X_{-\infty:-1})(\varphi_{k,n}(X_{-\infty:-1}))$
with $j,k\in F$ and $k\neq j$ and $1\leq n,\ell\leq L$. With this notation,
one can verify that

$\alpha=\frac{\eta}{2}+\frac{\eta(\eta-1)}{4}=\frac{\eta}{4}+\frac{\eta^{2}}{4},\
\beta=\frac{\eta^{2}}{4}\ \mbox{and}\
{\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}(G)=\begin{pmatrix}\alpha&\beta&\beta&...&\beta\\\
\beta&\alpha&\beta&...&\beta\\\ &&&...&\\\
\beta&\beta&...&\beta&\alpha\end{pmatrix}.$

Hence, the smallest eigenvalue of
${\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}(G)$ is
$\alpha-\beta=\frac{\eta}{4}$ which grows with $\eta=\frac{m}{K}$. This seems
also reasonable since once looking for cumulative effects, the larger the bin
size $\eta$, the more points you see in it and the more diverse the situations
are (hence the dictionary has many different functions) whereas if $\eta$ is
small there is a large probability to see all $\varphi_{j,\ell}$’s null.

Thus, Lemma 2 implies that eigenvalue of ${\mathbb{E}}(G)$ can be lower
bounded by

$\kappa^{\prime}=\frac{\eta}{4}(2\mu)^{\eta K|F|}.$

Choosing for some fixed integer $\eta$

$m=\eta K\mbox{ with }K\leq\sqrt{\log\log T}\mbox{ and }|F|\leq\log\log T,$
(5.3)

gives $\kappa^{\prime}$ of the order $(\log(T))^{-c_{3}}$ for some other
constant $c_{3}>0$ depending on $\mu$ and $\eta$.

##### Cumulative effect with spontaneous apparition

With the same notation of the previous example, one can show that

${\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}(G)=\begin{pmatrix}1&\eta/2&\eta/2&...&\eta/2\\\
\eta/2&\alpha&\beta&...&\beta\\\ &&...&&\\\
\eta/2&\beta&...&\beta&\alpha\end{pmatrix}.$

Reasoning by block with the vector $(\mu,a)$ with $\mu\in{\mathbb{R}}$ and
$a\in{\mathbb{R}}^{K|F|}$, we end up with

$(\mu,a)^{\intercal}{\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}(G)(\mu,a)=\left(\mu+\frac{\eta}{2}\sum_{j\in
F,k=1,...,K}a_{j,k}\right)^{2}+\frac{\eta}{4}\|a\|_{2}^{2}.$

But for all $0<\theta<1$,

$\displaystyle\left(\mu+\frac{\eta}{2}\sum
a_{j,k}\right)^{2}+\frac{\eta}{4}\|a\|_{2}^{2}$ $\displaystyle\geq$
$\displaystyle(1-\theta)\mu^{2}+\left(1-\frac{1}{\theta}\right)\frac{\eta^{2}}{4}\left(\sum_{j\in
F,k=1,...,K}a_{j,k}\right)^{2}+\frac{\eta}{4}\|a\|_{2}^{2}$
$\displaystyle\geq$
$\displaystyle(1-\theta)\mu^{2}-\frac{1-\theta}{\theta}\frac{K|F|\eta^{2}}{4}\|a\|_{2}^{2}+\frac{\eta}{4}\|a\|_{2}^{2}$

By choosing $\theta=\frac{2\eta K|F|}{1+2\eta K|F|}$ we conclude, thanks to
Lemma 2, that the smallest eigenvalue of ${\mathbb{E}}(G)$ can be lower
bounded by

$\kappa^{\prime}=(2\mu)^{\eta K|F|}\min\left(\frac{1}{1+2\eta
K|F|},\frac{\eta}{8}\right).$

Once again choosing for some fixed integer $\eta$

$m=\eta K\mbox{ with }K\leq\sqrt{\log\log T}\mbox{ and }|F|\leq\log\log T,$
(5.4)

gives $\kappa^{\prime}$ roughly larger than $(\log(T))^{-c_{3}}$ for some
other constant $c_{3}>0$ depending on $\mu$ and $\eta$.

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

######  Corollary 1.

Let $\Phi$ 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 ${\bf 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

$\|\hat{f}-p_{i}(\cdot)\|^{2}_{T}\leq\inf_{a\in{\mathbb{R}}^{\Phi}}\left\\{\|f_{a}-p_{i}(\cdot)\|^{2}_{T}+c_{2}|S(a)|\frac{(\log(T))^{c_{3}}}{T}\right\\},$

where the constant $c_{1}>0$ depends only on the underlying distribution of X,
$c_{2}>0$ depends on $\eta$ and $\gamma$ and constant $c_{3}>0$ depends on
both the underlying distribution of X and $\eta$.

Note that the main improvement with respect to Hansen, Reynaud-Bouret and
Rivoirard (2015), is that in all the examples , the constant $\kappa$ 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 $\varphi(X_{F,-m:-1})$’s are just the $X_{j,s}$ for $j\in F$
and $s\in\underline{m}$ and one can prove the following result.

######  Theorem 6.

For a finite $F\subset I$ and integer $T>m\geq 1$, let $X_{F,-(m-1):T}$ be a
sample produced by the stationary sparse space-time process ${\bf
X}=(X_{i,t})_{i\in I,t\in{\mathbb{Z}}}$ satisfying Assumptions 1, 2, 3 and 4.
For the Hawkes dictionary without spontaneous part, i.e.
$\varphi=\varphi_{j,s}$ with $\varphi_{j,s}(X_{F,-m:-1})=X_{j,s}$ for $j\in F$
and $s\in\underline{m}$, the corresponding Gram matrix $G$ defined by (3.2)
satisfies for all $c>0$, $s\leq m|F|$ and $T$ large enough, the property ${\bf
RE}(\kappa,c,s)$ on an event of probability larger than
$1-\frac{c^{\prime}}{T}-\delta$ with

$\kappa=\mu-\mu^{2}-((1-2\mu)+R_{T})(1+c)s,$

where

$R_{T}=\frac{c_{1}}{T^{1/2}}(m+\log T+\log|F|)^{1/2}(\log
m+\log|F|+\log\delta^{-1})^{1/2},$

for some positive constant $c^{\prime}$ and $c_{1}$ which only depends on the
underlying distribution of ${\bf X}$.

The major point to note is that asymptotically, for slowly growing $m$ and
$|F|$ as functions of $T$, the constant $\kappa$ 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 Hansen, Reynaud-Bouret and
Rivoirard (2015) which depends on the total number of neurons in the network.
For each fixed $c$ and $s$, we only need here $\mu$ to be close enough to
$1/2$ to have $\kappa>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.

##  6 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 $\lambda_{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
$\lambda_{i}$ but the fact that the $\lambda_{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.

##  7 Proofs

###  7.1 Proof of Theorem 1

To prove Theorem 1 we use arguments from Gaïffas and Guilloux (2012). We will
need the following Lemmas.

######  Lemma 3.

Let $\hat{f}=f_{\hat{a}}$ where $\hat{a}$ is defined by (3.3). For any vector
$a\in{\mathbb{R}}^{\Phi}$, the following inequality holds

$2\langle\hat{f}-f_{a},\hat{f}-p_{i}\rangle_{T}+\gamma
d|\hat{a}_{S^{c}(a)}|_{1}\leq\gamma
d|\hat{a}_{S(a)}-a_{S(a)}|_{1}+2(b-\bar{b})^{T}(\hat{a}-a),$ (7.1)

where $S(a)=\\{\varphi:a_{\varphi}\neq 0\\}$ and the vectors
$b,\bar{b}\in{\mathbb{R}}^{\Phi}$ are defined in (3.2) and (3.4) respectively.

###### Proof.

Throughout the proof we write $\partial 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\in\partial g(p)$.
Now since $\hat{a}$ is such that

$\hat{a}\in\ \arg\min_{a\in{\mathbb{R}}^{\Phi}}\\{a^{T}Ga-2a^{T}b+\gamma
d|a|_{1}\\},$

it follows that

$0\in\partial(\hat{a}^{T}G\hat{a}-2\hat{a}^{T}b+\gamma
d|\hat{a}|_{1})=2G\hat{a}-2b+\gamma d\partial|\hat{a}|_{1}.$

Thus, it follows that for some $\hat{w}\in\partial|\hat{a}|_{1}$, the
following equation holds

$2G\hat{a}-2b+\gamma d\hat{w}=0,$

which implies then

$(2G\hat{a}-2b+\gamma d\hat{w})^{T}(\hat{a}-a)=0,\ \mbox{for any}\
a\in{\mathbb{R}}^{\Phi}.$

From the above equation we can deduce that for any vector
$w\in\partial|a|_{1}$ and $a\in{\mathbb{R}}^{\Phi}$,

$(2G\hat{a}-2\bar{b})^{T}(\hat{a}-a)+\gamma
d(\hat{w}-w)^{T}(\hat{a}-a)=-\gamma
dw^{T}(\hat{a}-a)+2(b-\bar{b})^{T}(\hat{a}-a).$ (7.2)

One can easily show by the definition of subdifferentials that

$(\hat{w}-w)^{T}(\hat{a}-a)\geq 0,$

for all $\hat{w}\in|\hat{a}|_{1}$ and $w\in|a|_{1}.$ Thus, using this fact in
equation (7.2) together with the fact that
$(2G\hat{a}-2\bar{b})^{T}(\hat{a}-a)=2\langle\hat{f}-f_{a},\hat{f}-p_{i}\rangle_{T}$,
we derive the following inequality

$2\langle\hat{f}-f_{a},\hat{f}-p_{i}\rangle_{T}\leq-\gamma
dw^{T}(\hat{a}-a)+2(b-\bar{b})^{T}(\hat{a}-a).$ (7.3)

It is well know that

$\partial|a|_{1}=\\{v:|v|_{\infty}\leq 1\ \mbox{and}\ v^{T}a=|a|_{1}\\}.$

In other words, $v\in\partial|a|_{1}$ if and only if
$v_{\varphi}=\mbox{sign}(a_{\varphi})$ for ${\varphi}\in S(a)$ and
$v_{\varphi}\in[-1,1]$ for all ${\varphi}\in S^{c}(a).$ Now, take
$w=(w_{\varphi})_{\varphi\in\Phi}\in\partial|a|_{1}$ of the following form

$w_{\varphi}=\begin{cases}\mbox{sign}(a_{\varphi}),\ \mbox{if}\ {\varphi}\in
S(a)\\\ \mbox{sign}(\hat{a}_{\varphi}),\ \mbox{if}\ {\varphi}\in
S^{c}(a)\end{cases},$

and observe that $w^{T}(\hat{a}-a)=\sum_{\varphi\in
S(a)}\mbox{sign}(a_{\varphi})(\hat{a}_{\varphi}-a_{\varphi})+|\hat{a}_{S^{c}(a)}|_{1}$.
Thus, by plugging this identify into inequality (7.3), we obtain that

$2\langle\hat{f}-f_{a},\hat{f}-p_{i}\rangle_{T}+\gamma
d|\hat{a}_{S^{c}(a)}|_{1}\leq-\gamma d\sum_{\varphi\in
S(a)}\mbox{sign}(a_{\varphi})(\hat{a}_{\varphi}-a_{\varphi})+2(b-\bar{b})^{T}(\hat{a}-a),$

and the result follows, because $|-\sum_{\varphi\in
S(a)}\mbox{sign}(a_{\varphi})(\hat{a}_{\varphi}-a_{\varphi})|\leq|\hat{a}_{S(a)}-a_{S(a)}|_{1}.$
∎

######  Lemma 4.

Let $\hat{f}=f_{\hat{a}}$ where $\hat{a}$ defined by (3.3) with $\gamma\geq 2$
and $a\in{\mathbb{R}}^{\Phi}$. On an event on which

  1. (i)

$\langle\hat{f}-f_{a},\hat{f}-p_{i}\rangle_{T}\geq 0$,

  2. (ii)

$|b_{\varphi}-\bar{b}_{\varphi}|\leq d$ for all $\varphi\in\Phi,$

the following inequality is satisfied,

$|\hat{a}_{S^{c}(a)}|_{1}\leq\frac{\gamma+2}{\gamma-2}|\hat{a}_{S(a)}-a_{S(a)}|_{1},$
(7.4)

where $S(a)=\\{\varphi:a_{\varphi}\neq 0\\}$.

###### Proof.

Suppose that $\langle\hat{f}-f_{a},\hat{f}-p_{i}\rangle_{T}\geq 0$. In this
case, Lemma 3 implies that

$\gamma d|\hat{a}_{S^{c}(a)}|_{1}\leq\gamma
d|\hat{a}_{S(a)}-a_{S(a)}|_{1}+2\sum_{\varphi\in
S(a)}(b_{\varphi}-\bar{b}_{\varphi})(\hat{a}_{\varphi}-a_{\varphi})+2\sum_{\varphi\in
S^{c}(a)}(b_{\varphi}-\bar{b}_{\varphi})\hat{a}_{\varphi}.$

On an event on which $|b_{\varphi}-\bar{b}_{\varphi}|\leq d$ for all
$\varphi\in\Phi$, we then have that

$\gamma
d|\hat{a}_{S^{c}(a)}|_{1}\leq(\gamma+2)d|\hat{a}_{S(a)}-a_{S(a)}|_{1}+2d|\hat{a}_{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 $\langle\hat{f}-f_{a},\hat{f}-p_{i}\rangle_{T}<0$, there is
nothing to be proved, since in this case

$\|\hat{f}-p_{i}\|^{2}_{T}+\|\hat{f}-f_{a}\|^{2}_{T}-\|f_{a}-p_{i}\|^{2}_{T}=\langle\hat{f}-f_{a},\hat{f}-p_{i}\rangle_{T}<0.$

Hence, in what follows, take $a=(a_{\varphi})_{\varphi\in\Phi}$ such that
$|S(a)|\leq s$ and $\langle\hat{f}-f_{a},\hat{f}-p_{i}\rangle_{T}\geq 0$. In
this case, thanks to Lemma 4, we can use Property ${\bf
RE}(\kappa,c(\gamma),s)$ to the vector $\hat{a}-a:$

$\|\hat{a}_{S(a)}-a_{S(a)}\|^{2}\leq\kappa^{-1}(\hat{a}-a)^{T}G(\hat{a}-a).$

Now, as in the proof of Lemma 4, we know that on an event on which
$|b_{\varphi}-\bar{b}_{\varphi}|\leq d$ for all $\varphi\in\Phi$, the
following bound holds:

$2|(b-\bar{b})^{T}(\hat{a}-a)|\leq
2d|(\hat{a}_{S(a)}-a_{S(a)})|_{1}+2d|\hat{a}_{S^{c}(a)}|_{1}$

By using this inequality together with Lemma 3, we conclude that

$2\langle\hat{f}-f_{a},\hat{f}-p_{i}\rangle_{T}+(\gamma-2)d|\hat{a}_{S^{c}(a)}|_{1}\leq(\gamma+2)d|\hat{a}_{S(a)}-a_{S(a)}|_{1}.$
(7.5)

Finally, by Cauchy-Schwartz inequality, we know that

$|\hat{a}_{S(a)}-a_{S(a)}|_{1}\leq\sqrt{S(a)}\|\hat{a}_{S(a)}-a_{S(a)}\|\leq\sqrt{S(a)\kappa^{-1}(\hat{a}-a)^{T}G(\hat{a}-a)}.$

Plugging this last inequality into (7.5), we deduce that

$2\langle\hat{f}-f_{a},\hat{f}-p_{i}\rangle_{T}+(\gamma-2)d|\hat{a}_{S^{c}(a)}|_{1}\leq(\gamma+2)d\sqrt{S(a)\kappa^{-1}(\hat{a}-a)^{T}G(\hat{a}-a)}.$

To conclude the proof of the first part, note that

$\begin{cases}2\langle\hat{f}-f_{a},\hat{f}-p_{i}\rangle_{T}=\|\hat{f}-p_{i}\|^{2}_{T}+\|\hat{f}-f_{a}\|^{2}_{T}-\|f_{a}-p_{i}\|^{2}_{T}\\\
(\hat{a}-a)^{T}G(\hat{a}-a)=\|\hat{f}-f_{a}\|^{2}_{T},\end{cases}$

and use the inequality $qy-y^{2}\leq q^{2}/4$, which is valid for any $q,y>0.$

For the second part of the result, to control the fluctuations of
$b_{\varphi}-\bar{b}_{\varphi}$, let us note that
$b_{\varphi}-\bar{b}_{\varphi}=M_{T},$ where $(M_{t})_{1\leq t\leq T}$ is the
martingale defined by

$M_{t}=\sum_{i=1}^{t}\frac{\varphi(X_{-\infty:t-1})}{T}\left[X_{i,t}-p_{i}(X_{-\infty:t-1})\right].$

We can apply the classical bound of Hoeffding’s inequality on each increment
of the martingale $\Delta M_{t}$. Note that if $\varphi(X_{-\infty:t-1})$ is
positive,

$-\frac{\varphi(X_{-\infty:t-1})}{T}p_{i}(X_{-\infty:t-1})\leq\Delta
M_{t}\leq\frac{\varphi(X_{-\infty:t-1})}{T}[1-p_{i}(X_{-\infty:t-1})],$

and if $\varphi(X_{-\infty:t-1})$ is negative,

$\frac{\varphi(X_{-\infty:t-1})}{T}[1-p_{i}(X_{-\infty:t-1})]\leq\Delta
M_{t}\leq-\frac{\varphi(X_{-\infty:t-1})}{T}p_{i}(X_{-\infty:t-1}).$

This leads for every $\theta>0$ to

${\mathbb{E}}(e^{\theta\Delta
M_{t}}|X_{-\infty:t-1})\leq\exp\left(\frac{\theta^{2}\varphi(X_{-\infty:t-1})^{2}}{8T^{2}}\right)\leq\exp\left(\frac{\theta^{2}\|\Phi\|^{2}}{8T^{2}}\right).$

Therefore

${\mathbb{E}}(e^{\theta
M_{T}})\leq\exp\left(\frac{\theta^{2}\|\Phi\|^{2}}{8T}\right).$

Hence

${\mathbb{P}}(M_{T}\geq
x)\leq\exp\left(\frac{\theta^{2}\|\Phi\|_{\infty}^{2}}{8T}-\theta x\right).$

By optimizing this in $\theta$ and applying the same inequality to $-\varphi$,
we get for all positive $u$

${\mathbb{P}}\left(M_{T}\geq\sqrt{\frac{u\|\Phi\|^{2}_{\infty}}{2T}}\right)\leq
e^{-u}\mbox{ and
}{\mathbb{P}}\left(|b_{\varphi}-\bar{b}_{\varphi}|\geq\sqrt{\frac{u\|\Phi\|^{2}_{\infty}}{2T}}\right)\leq
2e^{-u}$

Therefore taking $u=\log|\Phi|+\log(2\delta^{-1})$ and then applying the union
bound we obtain the result.

###  7.2 Proof of Proposition 1

Since $\\{N_{(i,t)}>\ell\\}=\\{|A^{\ell}_{i,t}|\geq 1\\}$, the Markov
inequality implies that

$\displaystyle{\mathbb{P}}\left(N_{i,t}>\ell\right)\leq{\mathbb{E}}\left[|A^{\ell}_{i,t}|\right].$

So let us prove by induction that
${\mathbb{E}}\left[|A^{\ell}_{i,t}|\right]\leq(\bar{m})^{\ell}$ for all
$\ell\geq 1$. For $\ell=1$, we have
${\mathbb{E}}\left[|A^{1}_{i,t}|\right]={\mathbb{E}}\left[|V_{i,t}|\right]=\bar{m}_{i}\leq\bar{m}$.
Next for $\ell>1$,

$\displaystyle{\mathbb{E}}\left[|A^{\ell}_{i,t}|~{}|~{}A^{\ell-1}_{i,t}\right]$
$\displaystyle\leq$ $\displaystyle\sum_{(j,s)\in
A^{\ell-1}_{i,t}}{\mathbb{E}}\left[|V_{j,s}^{\to s}|\right]$
$\displaystyle\leq$ $\displaystyle\sum_{(j,s)\in
C_{i,t}(\ell-1)}\bar{m}_{j}~{}~{}\leq~{}|A^{\ell-1}_{i,t}|~{}\bar{m}.$

To conclude the proof take the overall expectation and use the induction
assumption given by
${\mathbb{E}}\left[|A^{\ell-1}_{i,t}|\right]\leq(\bar{m})^{\ell-1}$.

###  7.3 Proof of Theorem 2

For any fixed $n\geq 1$, for all site $(i,t)$ let

$G_{i,t}^{n}=\cup_{m=1}^{n}A_{i,t}^{m}$

We adopt the convention that if $G_{i,t}^{n}=\emptyset$,
$\mathbb{T}(G_{i,t}^{n})=t$ and we consider the variable
$T^{n}_{i,t}=t-\mathbb{T}(G_{i,t}^{n})$ as well as its Laplace transform
$\Psi_{i}^{n}(\theta)={\mathbb{E}}(e^{\theta T^{n}_{i,t}}).$

Let us prove by induction that $\Psi_{i}^{n}(\theta)$ is finite and that

$\Psi^{n}(\theta)=\sup_{i}\Psi_{i}^{n}(\theta)\leq\bar{\lambda}(1+\varphi(\theta)+...+\varphi(\theta)^{n-2}){\bf
1}_{n>1}+\varphi(\theta)^{n-1}g(\theta),$ (7.6)

where $\bar{\lambda}=\sup_{i\in I}\lambda_{i}(\emptyset)$ and

$g(\theta)=\sup_{i\in I}\sum_{v\in\mathcal{V}}e^{\theta T(v)}\lambda_{i}(v).$

Note that $g(\theta)$ is finite as soon as $\varphi(\theta)$ is and that
$0\leq\bar{\lambda}\leq 1.$

For $n=1$, since for all $i$,
$\mathbb{T}(G^{1}_{i,t})=\mathbb{T}(A_{i,t}^{1})=\mathbb{T}(K_{i,t})=t-T(V_{i,t})$

$\displaystyle\Psi_{i}^{1}(\theta)$ $\displaystyle=$
$\displaystyle{\mathbb{E}}\left(\exp\left[\theta T(V_{i,t})\right]\right)$
$\displaystyle=$ $\displaystyle\sum_{v\in\mathcal{V}}e^{\theta
T(v)}\lambda_{i}(v)$ $\displaystyle\leq$ $\displaystyle g(\theta).$

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_{i,t}^{n}$ are computed
recursively, we have that when $K_{i,t}$ is not empty,

$\mathbb{T}(G_{i,t}^{n+1})=\min_{(k,r)\in K_{i,t}}\mathbb{T}(G_{k,r}^{n}).$

Therefore if $K_{i,t}=\emptyset$, $T^{n+1}_{i,t}=0$ and

${\mathbb{E}}\left(\exp\left[\theta
T^{n+1}_{i,t}\right]~{}~{}|~{}~{}K_{i,t}\right)=1.$

This happens with probability $\lambda_{j}(\emptyset).$ If
$K_{i,t}\neq\emptyset,$

$\displaystyle{\mathbb{E}}\left(\exp\left[\theta\left(t-\mathbb{T}(G_{i,t}^{n+1})\right)\right]~{}~{}|~{}~{}K_{j,t}\right)$
$\displaystyle=$
$\displaystyle{\mathbb{E}}\left(\exp\left[\theta\max_{(k,r)\in
K_{i,t}}\left(t-\mathbb{T}(G_{k,r}^{n})\right)\right]~{}~{}|~{}~{}K_{i,t}\right)$
$\displaystyle\leq$ $\displaystyle\sum_{(k,r)\in
K_{i,t}}e^{\theta(t-r)}{\mathbb{E}}\left(\exp\left[\theta\left(r-\mathbb{T}(G_{k,r}^{n})\right)\right]~{}~{}|~{}~{}K_{i,t}\right).$

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^{\prime},r^{\prime}}$ for
$k^{\prime}\in I,r^{\prime}\leq r$ and $r<t$, it follows that
$\mathbb{T}(G^{n}_{k,r})$ is independent of $K_{i,t}.$ Hence if
$K_{i,t}\neq\emptyset$

$\displaystyle{\mathbb{E}}\left(\exp\left[\theta
T^{n+1}_{i,t}\right]~{}~{}|~{}~{}K_{j,t}\right)$ $\displaystyle\leq$
$\displaystyle\sum_{(k,r)\in K_{i,t}}e^{\theta(t-r)}\Psi_{k}^{n}(\theta)$
$\displaystyle\leq$ $\displaystyle\left[\sum_{(k,r)\in
K_{i,t}}e^{\theta(t-r)}\right]\Psi^{n}(\theta)$ $\displaystyle\leq$
$\displaystyle\left[|K_{i,t}|e^{\theta(t-\mathbb{T}(K_{j,t}))}\right]\Psi^{n}(\theta)$
$\displaystyle\leq$ $\displaystyle|V_{i,t}|e^{\theta
T(V_{i,t})}\Psi^{n}(\theta).$

We obtain by taking the overall expectation that

$\Psi_{i}^{n+1}(\theta)\leq\bar{\lambda}+\varphi(\theta)\Psi^{n}(\theta),$

so that $\sup_{i\in I}\Psi_{i}^{n+1}(\theta)$ 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, $\Psi_{i}^{n}(\theta)\to_{n\to\infty}\Psi_{i}(\theta)$ which are
therefore upper bounded by $\bar{\lambda}/(1-\varphi(\theta)).$ This concludes
the proof.

###  7.4 Proof of Lemma 1

We use the perfect simulation algorithm to construct these chains. Let ${\bf
U^{0}}=(U^{0,1}_{i,t},U^{0,2}_{i,t})_{i\in I,t\in{\mathbb{Z}}},\ldots,{\bf
U^{2k+1}}=(U^{2k+1,1}_{i,t},U^{2k+1,2}_{i,t})_{i\in I,t\in{\mathbb{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 $(\tilde{\Omega},\tilde{\mathcal{F}},\tilde{{\mathbb{P}}})$ to
be this common probability space.

The perfect simulation algorithm performed with the same field ${\bf U^{0}}$
on each site $(i,t)$ yields the construction of ${\bf X}=(X_{i,t})_{i\in
I,t\in{\mathbb{Z}}}$.

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

$\left((U^{n,1}_{i,t},U^{n,2}_{i,t})_{i\in
I,t\leq(n-2)B},(U^{0,1}_{i,t},U^{0,2}_{i,t})_{i\in I,(n-2)B<t\leq
nB},(U^{n,1}_{i,t},U^{n,2}_{i,t})_{i\in I,t>nB}\right),$

for $1\leq n\leq 2k$ and for $n=2k+1$,

$\left((U^{n,1}_{i,t},U^{n,2}_{i,t})_{i\in
I,t\leq(2k-1)B},(U^{0,1}_{i,t},U^{0,2}_{i,t})_{i\in I,(2k-1)B<t\leq
T},(U^{n,1}_{i,t},U^{n,2}_{i,t})_{i\in I,t>T}\right).$

Since all chains are simulated with the same set of weights
$(\lambda_{i})_{i\in I}$ and transitions $(p_{i}^{v})_{i\in
I,v\in\mathcal{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 ${\bf X}$ and
$\mathbb{T}_{i,t}=\mathbb{T}(G_{i,t})$. For any $n$, any $i\in F$ and any
$t\in I_{n}$, if $\mathbb{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 $\Omega_{good}=\cap_{i\in F}\cap_{n=1}^{2k+1}\cap_{t\in
I_{n}}\\{\mathbb{T}_{i,t}>(n-2)B\\}$, $X_{F,I_{n}}=X^{n}_{F,I_{n}}$ for all
$n=1,...,2k+1$. Note that $\Omega_{good}$ only depends on ${\bf X}$.

It remains to control $\tilde{{\mathbb{P}}}(\Omega^{c}_{good})$. By a union
bound, and the application of Theorem 2, we obtain

$\displaystyle\tilde{{\mathbb{P}}}(\Omega^{c}_{good})$ $\displaystyle\leq$
$\displaystyle\sum_{i\in F}\sum_{n=1}^{2k+1}\sum_{t\in
I_{n}}{\mathbb{P}}(\mathbb{T}_{i,t}\leq(n-2)B)$ $\displaystyle\leq$
$\displaystyle\sum_{i\in F}\sum_{n=1}^{2k+1}\sum_{t\in
I_{n}}{\mathbb{P}}(t-\mathbb{T}_{i,t}\geq t-(n-2)B)$ $\displaystyle\leq$
$\displaystyle\sum_{i\in F}\sum_{n=1}^{2k+1}\sum_{t\in
I_{n}}e^{-\theta(t-(n-2)B)}\Psi(\theta)$ $\displaystyle\leq$
$\displaystyle|F|(2k+1)\frac{e^{-\theta(B-m+1)}}{1-e^{-\theta}}\Psi(\theta).$

In particular if we choose $B=m+\theta^{-1}(2\log(T)+\log(|F|)$,

$\tilde{{\mathbb{P}}}(\Omega^{c}_{good})\leq\frac{2k+1}{T^{2}}\frac{\Psi(\theta)}{1-e^{-\theta}},$

which concludes the proof.

###  7.5 Proof of Theorem 3

Take $B=m+\theta^{-1}(2\log(T)+\log(|F|))$, $k=\lfloor\frac{T}{2B}\rfloor$ and
use the probability space
$(\tilde{\Omega},\tilde{\mathcal{F}},\tilde{{\mathbb{P}}})$ and the stochastic
chains ${\bf X},\ldots,{\bf X^{2k+1}}$ given by Lemma 1. By Lemma 1-Item 1 we
can assume that $Z$ is also defined on
$(\tilde{\Omega},\tilde{\mathcal{F}},\tilde{{\mathbb{P}}})$. Define also a
partition $J_{1},\ldots,J_{2k+1}$ of $1:T$ as follows:

$J_{n}=\\{1+(n-1)B,\ldots,nB\\}\ \mbox{for}\ 1\leq n\leq 2k,\ \mbox{and}\
J_{2k+1}=\\{1+2kB,\ldots,T\\}.$

For each $1\leq n\leq 2k+1$, write $S_{n}=\frac{1}{T}\sum_{t\in
J_{n}}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}|\leq B$ for all $1\leq n\leq
2k+1,$ it holds $|S_{n}|\leq MB/T$.

Observe that Lemma 1-Item 1 and 4 ensure that on $\Omega_{good},$

$Z=\sum_{n=1}^{2k+1}(S_{n}-{\mathbb{E}}(S_{n})),$

so that for any $w>0$, we have

$\tilde{{\mathbb{P}}}(Z>w)\leq\tilde{{\mathbb{P}}}(\Omega^{c}_{good})+\tilde{{\mathbb{P}}}\left(\sum_{n=1}^{2k+1}(S_{n}-{\mathbb{E}}(S_{n}))>w\right)\leq\frac{c^{\prime}(\theta)}{T}+\tilde{{\mathbb{P}}}\left(\sum_{n=1}^{2k+1}(S_{n}-{\mathbb{E}}(S_{n}))>w\right).$

Moreover, if we denote
$Z_{1}=\sum_{n=1}^{k+1}(S_{2n-1}-{\mathbb{E}}(S_{2n-1}))$ and
$Z_{2}=\sum_{n=1}^{k}(S_{2n}-{\mathbb{E}}(S_{2n})$, then

$\tilde{{\mathbb{P}}}\left(\sum_{n=1}^{2k+1}(S_{n}-{\mathbb{E}}(S_{n}))>u+v\right)\leq\tilde{{\mathbb{P}}}\left(Z_{1}>u\right)+\tilde{{\mathbb{P}}}\left(Z_{2}>v\right),$

for all $u+v=w$.

Lemma 1-Item 3 implies that $S_{2},\ldots,S_{2k}$ are independent, so that by
the classical Hoeffding inequality, we have for any $x>0$,
$\tilde{{\mathbb{P}}}\left(Z_{1}>\sqrt{kB^{2}M^{2}T^{-2}x/2}\right)\leq
e^{-x},$ and similarly for
$\tilde{{\mathbb{P}}}\left(Z_{1}>\sqrt{(k+1)B^{2}M^{2}T^{-2}x/2}\right)\leq
e^{-x}$. Hence

$\tilde{{\mathbb{P}}}\left(Z>\sqrt{kB^{2}M^{2}T^{-2}x/2}+\sqrt{(k+1)B^{2}M^{2}T^{-2}x/2}\right)\leq\frac{c^{\prime}(\theta)}{T}+2e^{-x}.$

But $k\leq T(2B)^{-1}$ and $k+1\leq(T+2B)(2B)^{-1}\leq T/B$. This leads
directly to the first result.

For the second result, note that we can restrict ourselves to $\Omega_{good}$
once and for all at the beginning and use the union bound only on the
auxiliary independent chains, which explains why we pay $|\mathcal{F}|$ only
in front of the deviation $e^{-x}$.

###  7.6 Proof of Theorem 4

Let $(\tilde{\Omega},\tilde{\mathcal{F}},\tilde{{\mathbb{P}}})$ be the
probability space and ${\bf X},\ldots,{\bf 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
$(\tilde{\Omega},\tilde{\mathcal{F}},\tilde{{\mathbb{P}}})$. We write
$\tilde{{\mathbb{E}}}$ to denote the expectation taken with respect the
probability measure $\tilde{{\mathbb{P}}}$.

Now, let $B$, $k$, $J_{1},\ldots,J_{2k+1}$ as in the proof of Theorem 3 and
define for $1\leq n\leq 2k+1$, the random matrix
$\Sigma_{n}=((\Sigma_{n}(f,g))_{f,g\in\mathcal{F}}$ as follows:

$\Sigma_{n}(f,g)=\frac{1}{T}\sum_{t\in
J_{n}}\left(f(X^{n}_{F,t-m:t-1})g(X^{n}_{F,t-m:t-1})-{\mathbb{E}}(f(X^{n}_{F,t-m:t-1})g(X^{n}_{F,t-m:t-1})\right).$

Clearly $\tilde{{\mathbb{E}}}(\Sigma_{n})=0$. To apply Theorem 1.3 of Tropp
(2012), we need to find a deterministic self-adjoint matrix $A_{n}$ such that
$A_{n}^{2}-\Sigma_{n}^{2}$ is non negative. This means that for all vector
$x\in{\mathbb{R}}^{\mathcal{F}}$,

$x^{\intercal}[A_{n}^{2}-\Sigma_{n}^{2}]x\geq 0.$

By taking $A_{n}=\sigma I_{n}$, it is sufficient to prove that

$x^{\intercal}\Sigma_{n}^{2}x\leq\sigma^{2}\|x\|^{2}.$

But

$\displaystyle x^{\intercal}\Sigma_{n}^{2}x$ $\displaystyle=$
$\displaystyle\sum_{f,g\in\mathcal{F}}x_{f}x_{g}\frac{1}{T^{2}}\sum_{t,t^{\prime}\in
J_{n}}\sum_{h\in\mathcal{F}}\left(f(X^{n}_{F,t-m:t-1})h(X^{n}_{F,t-m:t-1})-{\mathbb{E}}(f(X^{n}_{F,t-m:t-1})h(X^{n}_{F,t-m:t-1})\right)\times$
$\displaystyle\left(h(X^{n}_{F,t^{\prime}-m:t^{\prime}-1})g(X^{n}_{F,t^{\prime}-m:t^{\prime}-1})-{\mathbb{E}}(h(X^{n}_{F,t^{\prime}-m:t^{\prime}-1})g(X^{n}_{F,t^{\prime}-m:t^{\prime}-1})\right)$
$\displaystyle=$ $\displaystyle\frac{1}{T^{2}}\sum_{t,t^{\prime}\in
J_{n}}\sum_{h\in\mathcal{F}}\left[\sum_{f}x_{f}\left(f(X^{n}_{F,t-m:t-1})h(X^{n}_{F,t-m:t-1})-{\mathbb{E}}(f(X^{n}_{F,t-m:t-1})h(X^{n}_{F,t-m:t-1})\right)\right]\times$
$\displaystyle\left[\sum_{g}x_{g}\left(g(X^{n}_{F,t^{\prime}-m:t^{\prime}-1})h(X^{n}_{F,t^{\prime}-m:t^{\prime}-1})-{\mathbb{E}}(g(X^{n}_{F,t^{\prime}-m:t^{\prime}-1})h(X^{n}_{F,t^{\prime}-m:t^{\prime}-1})\right)\right]$
$\displaystyle\leq$ $\displaystyle\frac{1}{T^{2}}\sum_{t,t^{\prime}\in
J_{n}}\sum_{h\in\mathcal{F}}\|x\|^{2}\sqrt{\sum_{f}\left(f(X^{n}_{F,t-m:t-1})h(X^{n}_{F,t-m:t-1})-{\mathbb{E}}(f(X^{n}_{F,t-m:t-1})h(X^{n}_{F,t-m:t-1})\right)^{2}}\times$
$\displaystyle\sqrt{\sum_{g}\left(g(X^{n}_{F,t^{\prime}-m:t^{\prime}-1})h(X^{n}_{F,t^{\prime}-m:t^{\prime}-1})-{\mathbb{E}}(g(X^{n}_{F,t^{\prime}-m:t^{\prime}-1})h(X^{n}_{F,t^{\prime}-m:t^{\prime}-1})\right)^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{4\|x\|^{2}|\mathcal{F}|}{T^{2}}\sum_{t,t^{\prime}\in
J_{n}}\sum_{h\in\mathcal{F}}M^{4}$ $\displaystyle\leq$
$\displaystyle\frac{4|\mathcal{F}|^{2}B^{2}M^{4}}{T^{2}}\|x\|^{2}.$

Hence $\sigma=\frac{2|\mathcal{F}|BM^{2}}{T}$ works. Denote
$Z_{1}=\sum_{n=1}^{k+1}\Sigma_{2n-1}$ and $Z_{2}=\sum_{n=1}^{k}\Sigma_{2n}$.
Lemma 1 implies that on $\Omega_{good}$,

$Z=Z_{1}+Z_{2},$

so that by the triangle inequality we have for any $u>0$ and $v>0$,

$\tilde{{\mathbb{P}}}(\|Z\|>u+v)\leq\tilde{{\mathbb{P}}}(\Omega^{c}_{good})+\tilde{{\mathbb{P}}}(\|Z_{1}\|>u)+\tilde{{\mathbb{P}}}(\|Z_{2}\|>v).$

Since by Lemma 1-item 3, $\Sigma_{2},\Sigma_{4},\ldots,\Sigma_{2k}$ are i.i.d
random matrices, we can apply Theorem 1.3 of Tropp (2012) to deduce that for
any $v>0,$

$\tilde{{\mathbb{P}}}\left(\|Z_{2}\|>\sqrt{8k\sigma^{2}v}\right)\leq
2|\mathcal{F}|e^{-v},$

Similarly, we have that for any $x>0,$

$\tilde{{\mathbb{P}}}\left(\|Z_{2}\|>\sqrt{8(k+1)\sigma^{2}u}\right)\leq
2|\mathcal{F}|e^{-u},$

and as a consequence, it follows that for any $x>0,$

$\tilde{{\mathbb{P}}}\left(\|Z\|>\sqrt{8k\sigma^{2}x}+\sqrt{8(k+1)\sigma^{2}x}\right)\leq\frac{c^{\prime}(\theta)}{T}+4|\mathcal{F}|e^{-x}.$

Since $k^{1/2}+(k+1)^{1/2}\leq(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=\emptyset$, $f$ is
constant and
${\mathbb{E}}(f(X_{v}))={\mathbb{E}}_{\mathcal{B}(1/2}^{\otimes\mathcal{V}}(f(X_{v}))$.
Let $Q=\mathcal{B}(1/2)^{\otimes v}$.

If the time length of $v$ is strictly positive, let $t$ be the maximal time of
$v$ and let $w_{t}=\\{(i,t)\mbox{ for }i\mbox{ such that }(i,t)\in v\\}$.

$\displaystyle{\mathbb{E}}(f(X_{v}))$ $\displaystyle=$
$\displaystyle{\mathbb{E}}[{\mathbb{E}}(f(X_{v})|X_{-\infty:t-1})]$
$\displaystyle=$
$\displaystyle{\mathbb{E}}\left(\sum_{x_{w_{t}}\in\\{0,1\\}^{w_{t}}}f((X_{v\setminus
w_{t}},x_{w_{t}})){\mathbb{P}}(X_{w_{t}}=x_{w_{t}}|X_{-\infty:t-1})\right)$
$\displaystyle=$
$\displaystyle{\mathbb{E}}\left(\sum_{x_{w_{t}}\in\\{0,1\\}^{w_{t}}}f((X_{v\setminus
w_{t}},x_{w_{t}}))\prod_{i/(i,t)\in
w_{t}}{\mathbb{P}}(X_{i,t}=x_{i,t}|X_{-\infty:t-1})\right)$
$\displaystyle\geq$
$\displaystyle(2\mu)^{|w_{t}|}{\mathbb{E}}\left(\sum_{x_{w_{t}}\in\\{0,1\\}^{w_{t}}}f((X_{v\setminus
w_{t}},x_{w_{t}}))Q(X_{i,t}=x_{i,t})\right)$

But $\sum_{x_{w_{t}}\in\\{0,1\\}^{w_{t}}}f((X_{v\setminus
w_{t}}),x_{w_{t}}))Q(X_{i,t}=x_{i,t})$ is a cylindrical function on
$v\setminus w_{t}$ with time length strictly smaller than $v$, so by
induction,

$\displaystyle{\mathbb{E}}(f(X_{v}))$ $\displaystyle\geq$
$\displaystyle(2\mu)^{|w_{t}|}(2\mu)^{|v\setminus
w_{t}|}{\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}\left(\sum_{x_{w_{t}}\in\\{0,1\\}^{w_{t}}}f((X_{v\setminus
w_{t}}),x_{w_{t}}))Q(X_{i,t}=x_{i,t})\right)$ $\displaystyle\geq$
$\displaystyle(2\mu)^{|v|}{\mathbb{E}}_{\mathcal{B}(1/2)}^{\otimes\mathcal{V}}(f(X_{v})),$

which concludes the proof.

###  7.8 Proof of Theorem 5

For any $a\in{\mathbb{R}}^{\Phi}$ such that $\|a\|=1$, we have by Cauchy-
Schwarz inequality

$\kappa\leq a^{\intercal}{\mathbb{E}}(G)a\leq
a^{\intercal}Ga+\|a\|\|(G-{\mathbb{E}}(G))a\|\leq
a^{\intercal}Ga+\|G-{\mathbb{E}}(G)\|,$ (7.7)

so that the result follows from Theorem 4 with $x=\log(4|\mathcal{F}|/\delta)$
and $\mathcal{F}=\Phi$.

###  7.9 Proof of Theorem 6

First of all, remark that thanks to Lemma 2 and since $\varphi$ in this case
depends on a neighborhood of size 1, one has that

${\mathbb{E}}(G_{\varphi,\varphi})={\mathbb{E}}(\varphi(X)^{2})\geq 2\mu
1/2=\mu$

and similarly for $\varphi\not=\varphi^{\prime}$, $\varphi\varphi^{\prime}$ is
positive and depends on a neighborhood of size 2, hence

$(1-\mu)^{2}\geq{\mathbb{E}}(G_{\varphi,\varphi^{\prime}})\geq\mu^{2}.$

Moreover let us apply our version of Hoeffding’s inequality, i.e. the second
result of Theorem 3 on all the $\varphi^{2}=\varphi$,
$\varphi\varphi^{\prime}$ and $-\varphi\varphi^{\prime}$ for
$\varphi\not=\varphi^{\prime}$. Hence there exists and event of probability
larger than $1-\frac{c^{\prime}(\theta)}{T}-\delta$ such that for all
$\varphi,\varphi^{\prime}$,

$|G_{\varphi,\varphi^{\prime}}-{\mathbb{E}}(G_{\varphi,\varphi^{\prime}})|\leq
R_{T},$

with

$R_{T}=\sqrt{c"(\theta)\frac{(m+\log
T+\log|F|)}{T}\log\left(\frac{4|\Phi|^{2}}{\delta}\right)},$

which means that there exists a constant $c_{1}$ depending only on the
distribution such that for $T$ large enough (depending on $\theta$ and $|F|$)

$R_{T}=c_{1}T^{-1}(m+\log T+\log|F|)^{1/2}(\log
m+\log|F|+\log\delta^{-1})^{1/2}.$

Therefore on this event, for all $a$ and $J$ such that $|J|\leq s$ and
$|a_{J^{c}}|_{1}\leq c|a_{J}|_{1}$, and if $\mu^{2}\geq R_{T}$,

$\displaystyle a^{\intercal}Ga$ $\displaystyle=$
$\displaystyle\sum_{\varphi\in\Phi}a_{\varphi}^{2}G_{\varphi,\varphi}+\sum_{\varphi\not=\varphi^{\prime}\in\Phi}a_{\varphi}a_{\varphi^{\prime}}G_{\varphi,\varphi^{\prime}}$
$\displaystyle\geq$ $\displaystyle(\mu-
R_{T})\sum_{\varphi\in\Phi}a_{\varphi}^{2}+(\mu^{2}-R_{T})\sum_{\begin{matrix}\varphi\not=\varphi^{\prime}\in\Phi\\\
a_{\varphi}a_{\varphi^{\prime}}\geq
0\end{matrix}}a_{\varphi}a_{\varphi^{\prime}}+((1-\mu)^{2}+R_{T})\sum_{\begin{matrix}\varphi\not=\varphi^{\prime}\in\Phi\\\
a_{\varphi}a_{\varphi^{\prime}}<0\end{matrix}}a_{\varphi}a_{\varphi^{\prime}}$
$\displaystyle\geq$
$\displaystyle(\mu-\mu^{2})\|a\|^{2}+\mu^{2}\sum_{\varphi,\varphi^{\prime}\in\Phi}a_{\varphi}a_{\varphi^{\prime}}+(1-2\mu)\sum_{\begin{matrix}\varphi\not=\varphi^{\prime}\in\Phi\\\
a_{\varphi}a_{\varphi^{\prime}}<0\end{matrix}}a_{\varphi}a_{\varphi^{\prime}}-R_{T}|a|^{2}_{1}$
$\displaystyle\geq$
$\displaystyle(\mu-\mu^{2})\|a\|^{2}+\mu^{2}\left(\sum_{\varphi\in\Phi}a_{\varphi}\right)^{2}-((1-2\mu)-R_{T})|a|_{1}^{2}$
$\displaystyle\geq$
$\displaystyle(\mu-\mu^{2})\|a\|^{2}-((1-2\mu)+R_{T})\left[|a_{J}|_{1}+|a_{J^{c}}|_{1}\right]^{2}$
$\displaystyle\geq$
$\displaystyle(\mu-\mu^{2})\|a\|^{2}-((1-2\mu)+R_{T}))(1+c)^{2}|a_{J}|_{1}^{2}$
$\displaystyle\geq$
$\displaystyle(\mu-\mu^{2})\|a_{J}\|^{2}-((1-2\mu)+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 $\|\Phi\|_{\infty}=1$ and
$|\Phi|=|F|$. Hence, by applying Theorem 5 and Theorem 1 both with
$\delta=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

$\|\hat{f}-p_{i}(\cdot)\|^{2}_{T}\leq\inf_{a\in{\mathbb{R}}^{\Phi}}\left\\{\|f_{a}-p_{i}(\cdot)\|^{2}_{T}+4\kappa^{-1}|S(a)|\frac{(\log|F|+\log(2T))}{2T}\right\\},$
(7.8)

where $c_{1}$ depends only on the distribution of X and

$\kappa=\kappa^{\prime}-c^{\prime}_{1}T^{-1/2}|F|^{1/2}(m+\log(T)+\log|F|)^{1/2}(\log|F|+\log\delta^{-1})^{1/2},$

with $c^{\prime}_{1}$ depending only on the distribution of X and
$\kappa^{\prime}$ given by (5.1).

Now, for the choices given by (5.2), (5.3) and (5.4), then, as seen previously
$\kappa^{\prime}=c^{\prime}_{2}\log(T))^{-c_{3}^{\prime}}$, for positive
constants $c^{\prime}_{2}$ and $c^{\prime}_{3}$ depending only on $m$ and
$\mu$ and

$\kappa=\frac{c^{\prime}_{2}}{(\log T)^{c^{\prime}_{3}}}(1-o(1)).$

By plugging $\kappa$ into (7.8), the result follows.

## 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 UCAJedi
”Investissements d’Avenir” managed by the National Research Agency
(ANR-15-IDEX-01), by the structuring program $C@UCA$ 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.

## References

  * Basu and Michailidis (2015) [author] Basu, S.S. and Michailidis, G.G. (2015). Regularized Estimation in Sparse High-dimensional Time Series Models. Ann. Stat. 45 1535–1567.
  * Bühlmann and van de Geer (2011) [author] Bühlmann, P.P. and van de Geer, S.S. (2011). Statistics for High-Dimensional Data: Methods, Theory and Applications. Springer.
  * Candès and Tao (2005) [author] Candès, E.E. and Tao, T.T. (2005). Decoding by linear programming. IEEE Transactions on Information Theory 51 4203–4215.
  * Chen et al. (2017) [author] Chen, S.S., Shojaie, A.A., Shea-Brown, E.E. and Witten, D.D. (2017). The Multivariate Hawkes Process in High Dimensions: Beyond Mutual Excitation. Preprint Arxiv.
  * Chevallier (2015) [author] Chevallier, J.J. (2015). Mean-field limit of generalized Hawkes processes. Stoch. Proc. Appl 127 3870–3912.
  * Cofré and Cessac (2014) [author] Cofré, R.R. and Cessac, B.B. (2014). Exact computation of the maximum-entropy potential of spiking neural-network models. Phys. Rev. E 89\.
  * Comets, Fernandez and Ferrari (2002) [author] Comets, FrancisF., Fernandez, RobertoR. and Ferrari, Pablo A.P. A. (2002). Processes with long memory: Regenerative construction and perfect simulation. Ann. Appl. Probab. 12 921–943. 10.1214/aoap/1031863175
  * Duarte et al. (2016) [author] Duarte, A.A., Galves, A.A., Löcherbach, E.E. and Ost, G.G. (2016). Estimating the interaction graph of stochastic neural dynamics (to Appear in Bernoulli).
  * Fernandéz, Ferrari and Galves (2001) [author] Fernandéz, R.R., Ferrari, P.P. and Galves, A.A. (2001). Coupling, renewal and perfect simulation of chains of infinite order.
  * Gaïffas and Guilloux (2012) [author] Gaïffas, StéphaneS. and Guilloux, AgatheA. (2012). High-dimensional additive hazards models and the Lasso. Electron. J. Statist. 6 522–546. 10.1214/12-EJS681
  * Gaïffas and Matulewicz (2019) [author] Gaïffas, S.S. and Matulewicz, G.G. (2019). Sparse inference of the drift of a high-dimensional Ornstein-Uhlenbeck process. Journal of Multivariate Analysis 169 1–20.
  * Galves and Löcherbach (2013) [author] Galves, A.A. and Löcherbach, E.E. (2013). Infinite Systems of Interacting Chains with Memory of Variable Length—A Stochastic Model for Biological Neural Nets. Journal of Statistical Physics 151 896–921.
  * Galves and Löcherbach (2016) [author] Galves, A.A. and Löcherbach, E.E. (2016). Modeling networks of spiking neurons as interacting processes with memory of variable length. Journal de la Société Française de Statistiques 157 17-32.
  * Galves et al. (2013) [author] Galves, A.A., Garcia, N. L.N. L., Löcherbach, E.E. and Orlandi, E.E. (2013). Kalikow-type decomposition for multicolor infinite range particle systems. Ann. Appl. Probab. 23 1629–1659. 10.1214/12-AAP882
  * Hansen, Reynaud-Bouret and Rivoirard (2015) [author] Hansen, Niels RichardN. R., Reynaud-Bouret, PatriciaP. and Rivoirard, VincentV. (2015). Lasso and probabilistic inequalities for multivariate point processes. Bernoulli 21 83–143. 10.3150/13-BEJ562
  * Hodara and Löcherbach (2016) [author] Hodara, P.P. and Löcherbach, E.E. (2016). Hawkes Processes with variable length memory and an infinite number of components. To appear in Adv. Appl. Probab.
  * Hunt et al. (2018) [author] Hunt, X. J.X. J., Reynaud-Bouret, P.P., Rivoirard, V.V., Sansonnet, L.L. and Willett, R.R. (2018). A data-dependent weighted LASSO under Poisson noise. to appear in IEEE IEEE Transactions on Information Theory.
  * Jiang, Raskutti and Willett (2015) [author] Jiang, X.X., Raskutti, G.G. and Willett, R.R. (2015). Minimax optimal rates for poisson inverse prob- lems with physical constraints. IEEE Transactions on Information Theory 61 4458–4474.
  * Kalikow (1990) [author] Kalikow, SteveS. (1990). Random markov processes and uniform martingales. Israel Journal of Mathematics 71 33–54. 10.1007/BF02807249
  * Kelly et al. (2010) [author] Kelly, R. C.R. C., Smith, M. A.M. A., Kass, R. E.R. E. and Lee, T. S.T. S. (2010). Accounting for network effects in neuronal responses using L1 regularized point process models. NIPS – Advances in Neural Information Processing Systems 23 1099–1107.
  * Kock and Callot (2015) [author] Kock, A. B.A. B. and Callot, L.L. (2015). Oracle inequalities for high dimensional vector autoregressions. Journal of Econometrics 186 325–344.
  * Lerasle and Takahashi (2016) [author] Lerasle, M.M. and Takahashi, D. Y.D. Y. (2016). Sharp oracle inequalities and slope heuristic for specification probabilities estimation in general random fields. Bernoulli 22 325–344.
  * Mark, Raskutti and Willett (2018) [author] Mark, B.B., Raskutti, G.G. and Willett, R.R. (2018). Network estimation from point process data. Preprint Arxiv.
  * Mark, Raskutti and Willett (2019) [author] Mark, B.B., Raskutti, G.G. and Willett, R.R. (2019). Estimating Network Structure from Incomplete Event Data. Oral presentation AISTATS.
  * Pouzat and Chaffiol (2009) [author] Pouzat, C.C. and Chaffiol, A.A. (2009). Automatic spike train analysis and report generation. An implementation with R, R2HTML and STAR. J. Neurosci. Meth.
  * Reynaud-Bouret and Roy (2007) [author] Reynaud-Bouret, P.P. and Roy, E.E. (2007). Some non asymptotic tail estimates for Hawkes processes. Bulletin of the Belgian Mathematical Society-Simon Stevin 13 883–896.
  * Rudelson and Vershynin (2008) [author] Rudelson, M.M. and Vershynin, R.R. (2008). On sparse reconstruction from Fourier and Gaussian measurements. Comm. Pure Appl. Math. 61 1025–1045.
  * Sacerdote and Giraudo (2013) [author] Sacerdote, L.L. and Giraudo, M. T.M. T. (2013). Stochastic Biomathematical Models 2058 Stochastic Integrate and Fire Models: A Review on Mathematical Methods and Their Applications, 99–148. Lecture Notes in Mathematics, Springer.
  * Tropp (2012) [author] Tropp, Joel A.J. A. (2012). User-Friendly Tail Bounds for Sums of Random Matrices. Foundations of Computational Mathematics 12 389–434. 10.1007/s10208-011-9099-z
  * Tropp (2015) [author] Tropp, J.J. (2015). Sampling Theory, a Renaissance: Compressive sampling and other developments Convex recovery of a structured signal from independent random linear measurements. G. Pfander. Ser. Applied and Numerical Harmonic Analysis. Birkhaeuser, Basel.
  * van de Geer (2016) [author] van de Geer, S.S. (2016). Estimation and Testing under Sparsity. École d’été de Saint-Flour XLV, Springer.
  * van de Geer and Bühlmann (2009) [author] van de Geer, S.S. and Bühlmann, P.P. (2009). On the conditions used to prove oracle results for the Lasso. Electronic Journal of Statistics 3 1360–1392.
  * Viennet (1997) [author] Viennet, G.G. (1997). Inequalities for absolutely regular sequences: application to density estimation. Probability Theory and Related Fields 107 467–492.