Let us study $\bar{G}_M^{j' \to j}$. For $j'' = a \lor b \in \{j', j_1, j_2\}$, the conditional spiking probability of $Z_{m,t}^{j'',l}$ is $(-\frac{1}{2} + \frac{1}{2}(Z_{m,t-1}^{a,l} + Z_{m,t-1}^{b,l}))_+$. Then $j''$ spikes with probability $\frac{1}{2}$ if and only if neurons $a$ and $b$ spiked before. Let $j_1 = a_1 \lor a_2, j_2 = b_1 \lor b_2, j' = d_1 \lor d_2$. Let $c_l'$ is the number of distinct variables of layer $l'$ which intervene in the tensors $j_1, j_2$ and $j'$.

$$
\begin{align*}
\bar{G}_M^{j' \to j} &= \sum_{m=1}^{M} \mathbb{E}[Z_{m,t}^{j_1,l} Z_{m,t}^{j_2,l} Z_{m,t}^{j',l} | \mathcal{F}_{l-1}] \\
&= \sum_{m=1}^{M} \mathbb{E}\left[\frac{1}{2^{c_{l-1}^{j' \to j}}} Z_{m,t}^{a_1,l} Z_{m,t}^{a_2,l} Z_{m,t}^{b_1,l} Z_{m,t}^{b_2,l} Z_{m,t}^{d_1,l} Z_{m,t}^{d_2,l} | \mathcal{F}_{l-1}\right] \\
&\vdots \\
&= \sum_{m=1}^{M} 2^{-(c_{l-1}^{j' \to j} + c_{l-2}^{j' \to j} + \dots + c_1^{j' \to j})} \mathbb{E}\left[\prod_{i \in S(j_1) \cup S(j_2) \cup S(j)} X_{m,t}^{i,l} | \mathcal{F}_{l-1}\right] \\
&= \sum_{m=1}^{M} 2^{-(c_{l-1}^{j' \to j} + c_{l-2}^{j' \to j} + \dots + c_1^{j' \to j})} \prod_{i \in S(j_1) \cup S(j_2) \cup S(j)} \mathbb{E}[X_{m,t}^{i,l} | \mathcal{F}_{l-1}] \\
&= \sum_{m=1}^{M} 2^{-(c_{l-1}^{j' \to j} + c_{l-2}^{j' \to j} + \dots + c_1^{j' \to j})} \prod_{i \in S(j_1) \cup S(j_2) \cup S(j)} \mathbb{E}[X_{m,t}^{i,l}] \\
&= \sum_{m=1}^{M} 2^{-(c_{l-1}^{j' \to j} + c_{l-2}^{j' \to j} + \dots + c_1^{j' \to j})} \rho_m(S(j_1) \cup S(j_2) \cup S(j'))
\end{align*}
$$

because the variables $X_{m,t}^{i,l}$ are mutually independent knowing $\mathcal{F}_{l-1}$ and are independent of $\mathcal{F}_{l-1}$. Therefore, according to Assumption 13,

$$
\bar{G}_M^{j' \to j} = 2^{-(c_{l-1}^{j' \to j} + c_{l-2}^{j' \to j} + \dots + c_1^{j' \to j})} \rho(S(j') \cup S(j))M.
$$

There are two cases. If $\rho(S(j)) = 0$ then for all $j' \in \tilde{J}_{l-1}$, $\bar{G}_M^{j' \to j} = 0$. Let $w_{\infty}^{j' \to j} := \frac{1}{|\tilde{J}_{l-1}|}$. This definition does not conflict with the one given at the beginning of the proof because $j \notin \tilde{J}_l$ according to $\tilde{J}_l$ defined in Assumption 16. Then for all $j' \in \tilde{J}_{l-1}$,

$$
\bar{w}_{M+1}^{j' \to j} = w_{\infty}^{j' \to j}. \qquad (17)
$$

If $\rho(S(j)) > 0$ then according to the definition of $J_l$, $S(j_1) \cap S(j_2) = \emptyset$ so for $j' \in \{j_1, j_2\}$, $c_{l'}^{j' \to j} = 2^{l-l'}$ for any $l' \le l-1$. So $\bar{G}_M^{j' \to j} = 2^{-2l+2}\rho(S(j))M$. If $j' \notin \{j_1, j_2\}$ then $c_{l-1}^{j' \to j} = 3$, otherwise $c_{l-1}^{j' \to j} = 2$. Besides, it is clear that if $j' \in \{j_1, j_2\}$ and $j'' \notin \{j_1, j_2\}$ then for every $l' \le l-2$, $c_{l'}^{j' \to j} \le c_{l'}^{j'' \to j}$. In
addition, $\rho(S(j)) \ge \rho(S(j') \cup S(j))$ for any $j' \in \tilde{J}_{l-1}$. Therefore for $j' \ne j_1, j_2$, $\tilde{G}_M^{j' \to j} \le 2^{-2l+1}\rho(S(j))M$. Hence

$$ \arg\max_{j' \in \tilde{J}_{l-1}} 2^{-(c_{l-1}^{j' \to j} + c_{l-2}^{j' \to j} + \dots + c_1^{j' \to j})} \rho(S(j') \cup S(j))M = \{j_1, j_2\} $$

and

$$ \max_{j' \in \tilde{J}_{l-1}} 2^{-(c_{l-1}^{j' \to j} + c_{l-2}^{j' \to j} + \dots + c_1^{j' \to j})} \rho(S(j') \cup S(j)) \\ - \max_{j' \ne j_1, j_2} 2^{-(c_{l-1}^{j' \to j} + c_{l-2}^{j' \to j} + \dots + c_1^{j' \to j})} \rho(S(j') \cup S(j)) \ge 2^{-2l+1} \rho(S(j)). $$

Let $w_{\infty}^{j' \to j} := 1_{j' \in j_1 \lor j_2}$. According to Proposition 30, with $\eta^j = \sqrt{\frac{8 \ln(|\tilde{J}_{l-1}|)}{M}}$ we have for all $j' \in \tilde{J}_{l-1}$

$$ |\bar{w}_{M+1}^{j' \to j} - w_{\infty}^{j' \to j}| \le E_{\text{EWA}}^{j,l}(M, |\tilde{J}_{l-1}|). \quad (18) $$

Therefore, for $j = j_1 \lor j_2 \in J_l$,

* if $\rho(S(j)) = 0$ then by combining (17) and (16) we get

$$ \|w_{M+1}^j - w_\infty^j\|_2 \le E_{\text{prec}}(M, |\tilde{J}_{l-1}|, l-1) + E_{\text{approx}}(T, |\tilde{J}_{l-1}|, |\tilde{J}_{l-1}^{\vee 1}|, \alpha). $$

* if $\rho(S(j)) > 0$ then by combining (16) and (18) we get

$$ \|w_{M+1}^j - w_\infty^j\|_2 \le E_{\text{prec}}(M, |\tilde{J}_{l-1}|, l-1) + E_{\text{approx}}(T, |\tilde{J}_{l-1}|, |\tilde{J}_{l-1}^{\vee 1}|, \alpha) + \sqrt{|\tilde{J}_{l-1}|} E_{\text{EWA}}^{j,l}(M, |\tilde{J}_{l-1}|). $$

Now let us study the selection phase. Let $\mathcal{F}_l^{\text{learn}}$ be the $\sigma$-algebra generated by every event that happened until the end of the learning phase of layer $l$. Let $j \in J_l$. The variables $(X_{o,t}^{j,l})_{o \in \mathcal{O}, 1 \le t \le T}$ are independent knowing the $\sigma$-algebra $\mathcal{F}_l^{\text{learn}}$ since the weights $w_{M+1}^j$ are frozen and are $\mathcal{F}_l^{\text{learn}}$-measurable. Hence according to Proposition 29, there exists a set $D_{\text{sel}}^l$ of probability more than $1 - \alpha$ on which for every $j \in J_l, o \in \mathcal{O}$,

$$ \left| \langle X_{o,t}^{j,l} \rangle_{t \in [T]} - \mathbb{E}[X_{o,1}^{j,l} | \mathcal{F}_1^{\text{learn}}] \right| \le \sqrt{\frac{1}{2T} \ln \left( \frac{2|J_l| |\mathcal{O}|}{\alpha} \right)} $$

since $\mathbb{E}[X_{o,t}^{j,l} | \mathcal{F}_1^{\text{learn}}]$ does not depend on $t$.
addition, $\rho(S(j)) \ge \rho(S(j') \cup S(j))$ for any $j' \in \tilde{J}_{l-1}$. Therefore for $j' \ne j_1, j_2$, $\tilde{G}_M^{j' \to j} \le 2^{-2l+1}\rho(S(j))M$. Hence

$$ \arg\max_{j' \in \tilde{J}_{l-1}} 2^{-(c_{l-1}^{j' \to j} + c_{l-2}^{j' \to j} + \dots + c_1^{j' \to j})} \rho(S(j') \cup S(j))M = \{j_1, j_2\} $$

and

$$ \max_{j' \in \tilde{J}_{l-1}} 2^{-(c_{l-1}^{j' \to j} + c_{l-2}^{j' \to j} + \dots + c_1^{j' \to j})} \rho(S(j') \cup S(j)) \\ - \max_{j' \ne j_1, j_2} 2^{-(c_{l-1}^{j' \to j} + c_{l-2}^{j' \to j} + \dots + c_1^{j' \to j})} \rho(S(j') \cup S(j)) \ge 2^{-2l+1} \rho(S(j)). $$

Let $w_{\infty}^{j' \to j} := 1_{j' \in j_1 \lor j_2}$. According to Proposition 30, with $\eta^j = \sqrt{\frac{8 \ln(|\tilde{J}_{l-1}|)}{M}}$ we have for all $j' \in \tilde{J}_{l-1}$

$$ |\bar{w}_{M+1}^{j' \to j} - w_{\infty}^{j' \to j}| \le E_{\text{EWA}}^{j,l}(M, |\tilde{J}_{l-1}|). \quad (18) $$

Therefore, for $j = j_1 \lor j_2 \in J_l$,

* if $\rho(S(j)) = 0$ then by combining (17) and (16) we get

$$ \|w_{M+1}^j - w_\infty^j\|_2 \le E_{\text{prec}}(M, |\tilde{J}_{l-1}|, l-1) + E_{\text{approx}}(T, |\tilde{J}_{l-1}|, |\tilde{J}_{l-1}^{\vee 1}|, \alpha). $$

* if $\rho(S(j)) > 0$ then by combining (16) and (18) we get

$$ \|w_{M+1}^j - w_\infty^j\|_2 \le E_{\text{prec}}(M, |\tilde{J}_{l-1}|, l-1) + E_{\text{approx}}(T, |\tilde{J}_{l-1}|, |\tilde{J}_{l-1}^{\vee 1}|, \alpha) + \sqrt{|\tilde{J}_{l-1}|} E_{\text{EWA}}^{j,l}(M, |\tilde{J}_{l-1}|). $$

Now let us study the selection phase. Let $\mathcal{F}_l^{\text{learn}}$ be the $\sigma$-algebra generated by every event that happened until the end of the learning phase of layer $l$. Let $j \in J_l$. The variables $(X_{o,t}^{j,l})_{o \in \mathcal{O}, 1 \le t \le T}$ are independent knowing the $\sigma$-algebra $\mathcal{F}_l^{\text{learn}}$ since the weights $w_{M+1}^j$ are frozen and are $\mathcal{F}_l^{\text{learn}}$-measurable. Hence according to Proposition 29, there exists a set $D_{\text{sel}}^l$ of probability more than $1 - \alpha$ on which for every $j \in J_l, o \in \mathcal{O}$,

$$ \left| \langle X_{o,t}^{j,l} \rangle_{t \in [T]} - \mathbb{E}[X_{o,1}^{j,l} | \mathcal{F}_1^{\text{learn}}] \right| \le \sqrt{\frac{1}{2T} \ln \left( \frac{2|J_l||\mathcal{O}|}{\alpha} \right)} $$

since $\mathbb{E}[X_{o,t}^{j,l} | \mathcal{F}_1^{\text{learn}}]$ does not depend on $t$.
Let $(Z_{o,t}^{j,l})_{j \in \tilde{J}_1 \cup \dots \cup \tilde{J}_{l-1} \cup J_l, o \in O, 1 \le t \le T}$ be the coupled network activity with any weights $(w_{\star}^j)$ which are $\mathcal{F}_l^{\text{learn}}$-measurable as defined in section C.2. Then for $j \in J_l, o \in O$, similarly as in (13) we get

$$ \mathbb{E}[|X_{o,1}^{j,l} - Z_{o,1}^{j,l}| | \mathcal{F}_1^{\text{learn}}] \le \sum_{l'=1}^{l-1} \max_{a \in \tilde{J}_{l'}} \|w_{M+1}^a - w_{\star}^a\|_1 + \max_{a \in J_l} \|w_{M+1}^a - w_{\star}^a\|_1. $$

Let us work on $D^1 \cap D_{\text{sel}}^1 \cap \dots \cap D^l \cap D_{\text{sel}}^l$. Let $w_{\star}^j := w_{\infty}^j$ for $j \in \tilde{J}_1 \cup \dots \cup \tilde{J}_{l-1} \cup J_l$. Then we by Cauchy-Schwartz inequality we have

$$ \left| \langle X_{o,t}^{j,l} \rangle_{t \in [T]} - \mathbb{E}[Z_{o,1}^{j,l} | \mathcal{F}_1^{\text{learn}}] \right| \le \sqrt{\frac{1}{2T} \ln \left( \frac{2|J_l| |O|}{\alpha} \right)} + \sum_{l'=1}^{l} E_w(l') + \sqrt{|\hat{J}_{l'-1}|} \max_{a \in J_l} \|w_{M+1}^a - w_{\infty}^a\|_2 $$

where we control every term. Let us study $\mathbb{E}[Z_{o,1}^{j,l} | \mathcal{F}_1^{\text{learn}}]$. If $\rho(S(j)) > 0$ then similarly as in the computation of $\bar{G}_M^{j' \to j}$ we get that $\mathbb{E}[Z_{o,1}^{j,l} | \mathcal{F}_l^{\text{learn}}] = 2^{-2^l+1}\rho(S(j))$. If $\rho(S(j)) = 0$ then

$$ \mathbb{E}[Z_{o,t}^{j,l} | \mathcal{F}_l^{\text{learn}}] = \mathbb{E} \left[ \left( -\frac{1}{2} + \frac{1}{|\tilde{J}_{l-1}|} \sum_{j' \in \tilde{J}_{l-1}} Z_{o,t-1}^{j',l} \right)_+ | \mathcal{F}_l^{\text{learn}} \right]. $$

The computation in the case $\rho(S(j)) > 0$ also holds for neurons of layer $l-1$, which are all in this case because $\hat{J}_{l-1} = \tilde{J}_{l-1}$. Therefore, according to Assumption 17, at most half the neurons of layer $l-1$ are active when presented with $o$. Hence

$$ \mathbb{E}[Z_{o,1}^{j,l} | \mathcal{F}_1^{\text{learn}}] = 0 = 2^{-2^l+1}\rho(S(j)). $$

Therefore for all $j \in J_l, o \in O$,

$$ \left| \langle X_{o,t}^{j,l} \rangle_{t \in [T]} - 2^{-2^l+1} \rho(S(j)) \right| \le \sqrt{\frac{1}{2T} \ln \left( \frac{2|J_l| |O|}{\alpha} \right)} + \sum_{l'=1}^{l} E_w(l') + \sqrt{|\hat{J}_{l'-1}|} \max_{a \in J_l} \|w_{M+1}^a - w_{\infty}^a\|_2 := E(l, M, T) $$

Besides, according to Assumption 16, there exists $p_l > 0$ such that if $j \in \tilde{J}_l$ then there exists $o \in O$ such that $\rho_o(S(j)) \ge p_l$ and if $j \in J_l \setminus \tilde{J}_l$ then for all $o \in O$, $\rho_o(S(j)) < p_l$. Let $q_l := \max_{j \in J_l \setminus \tilde{J}_l} \rho_o(S(j))$. Let us choose the threshold $s_l := \frac{1}{2}(2^{-2^l+1}p_l + 2^{-2^l+1}q_l)$. Since $E(l, M, T) = O((\frac{M^{l-1}}{T})^{1/2} + e^{-C\sqrt{M}})$ then for $\frac{T}{M^{l-1}}$ and $M$ large enough,

$$ E(l, M, T) < \frac{1}{2}(2^{-2^l+1}p_l - 2^{-2^l+1}q_l). \quad (19) $$
Let $(Z_{o,t}^{j,l})_{j \in \tilde{J}_1 \cup \dots \cup \tilde{J}_{l-1} \cup J_l, o \in O, 1 \le t \le T}$ be the coupled network activity with any weights $(w_{\star}^j)$ which are $\mathcal{F}_l^{\text{learn}}$-measurable as defined in section C.2. Then for $j \in J_l, o \in O$, similarly as in (13) we get

$$ \mathbb{E}[|X_{o,1}^{j,l} - Z_{o,1}^{j,l}| | \mathcal{F}_1^{\text{learn}}] \le \sum_{l'=1}^{l-1} \max_{a \in \tilde{J}_{l'}} \|w_{M+1}^a - w_{\star}^a\|_1 + \max_{a \in J_l} \|w_{M+1}^a - w_{\star}^a\|_1. $$

Let us work on $D^1 \cap D_{\text{sel}}^1 \cap \dots \cap D^l \cap D_{\text{sel}}^l$. Let $w_{\star}^j := w_{\infty}^j$ for $j \in \tilde{J}_1 \cup \dots \cup \tilde{J}_{l-1} \cup J_l$. Then we by Cauchy-Schwartz inequality we have

$$ \left| \langle X_{o,t}^{j,l} \rangle_{t \in [T]} - \mathbb{E}[Z_{o,1}^{j,l} | \mathcal{F}_1^{\text{learn}}] \right| \le \sqrt{\frac{1}{2T} \ln \left( \frac{2|J_l| |O|}{\alpha} \right)} + \sum_{l'=1}^{l} E_w(l') + \sqrt{|\hat{J}_{l'-1}|} \max_{a \in J_l} \|w_{M+1}^a - w_{\infty}^a\|_2 $$

where we control every term. Let us study $\mathbb{E}[Z_{o,1}^{j,l} | \mathcal{F}_1^{\text{learn}}]$. If $\rho(S(j)) > 0$ then similarly as in the computation of $\bar{G}_M^{j' \to j}$ we get that $\mathbb{E}[Z_{o,1}^{j,l} | \mathcal{F}_l^{\text{learn}}] = 2^{-2^l+1}\rho(S(j))$. If $\rho(S(j)) = 0$ then

$$ \mathbb{E}[Z_{o,t}^{j,l} | \mathcal{F}_l^{\text{learn}}] = \mathbb{E} \left[ \left( -\frac{1}{2} + \frac{1}{|\tilde{J}_{l-1}|} \sum_{j' \in \tilde{J}_{l-1}} Z_{o,t-1}^{j',l} \right)_+ | \mathcal{F}_l^{\text{learn}} \right]. $$

The computation in the case $\rho(S(j)) > 0$ also holds for neurons of layer $l-1$, which are all in this case because $\hat{J}_{l-1} = \tilde{J}_{l-1}$. Therefore, according to Assumption 17, at most half the neurons of layer $l-1$ are active when presented with $o$. Hence

$$ \mathbb{E}[Z_{o,1}^{j,l} | \mathcal{F}_1^{\text{learn}}] = 0 = 2^{-2^l+1}\rho(S(j)). $$

Therefore for all $j \in J_l, o \in O$,

$$ \left| \langle X_{o,t}^{j,l} \rangle_{t \in [T]} - 2^{-2^l+1} \rho(S(j)) \right| \le \sqrt{\frac{1}{2T} \ln \left( \frac{2|J_l| |O|}{\alpha} \right)} + \sum_{l'=1}^{l} E_w(l') + \sqrt{|\hat{J}_{l'-1}|} \max_{a \in J_l} \|w_{M+1}^a - w_{\infty}^a\|_2 := E(l, M, T) $$

Besides, according to Assumption 16, there exists $p_l > 0$ such that if $j \in \tilde{J}_l$ then there exists $o \in O$ such that $\rho_o(S(j)) \ge p_l$ and if $j \in J_l \setminus \tilde{J}_l$ then for all $o \in O$, $\rho_o(S(j)) < p_l$. Let $q_l := \max_{j \in J_l \setminus \tilde{J}_l} \rho_o(S(j))$. Let us choose the threshold $s_l := \frac{1}{2}(2^{-2^l+1}p_l + 2^{-2^l+1}q_l)$. Since $E(l, M, T) = O((\frac{M^{l-1}}{T})^{1/2} + e^{-C\sqrt{M}})$ then for $\frac{T}{M^{l-1}}$ and $M$ large enough,

$$ E(l, M, T) < \frac{1}{2}(2^{-2^l+1}p_l - 2^{-2^l+1}q_l). \quad (19) $$
Hence there exists constants $C_1^l$ and $C_2^l$ such that for $\frac{T}{M^{l-1}} \ge C_1^l$ and $M \ge C_2^l$, (19) is true. Besides, $\frac{T}{M^{l-2}} \ge \frac{T}{M^{l-1}}$ so let us take $C_1^l \ge C_1^{l-1}$ and $C_2^l \ge C_2^{l-1}$ so that we still have $\frac{T}{M^{l-2}} \ge C_1^{l-1}$ and $M \ge C_2^{l-1}$. Under this condition and this choice of threshold, if $j \in \tilde{J}_l$ then $\langle X_{o,t}^{j,l} \rangle_{t \in [T]} \ge s_l$ and otherwise $\langle X_{o,t}^{j,l} \rangle_{t \in [T]} < s_l$ so $\hat{J}_l = \tilde{J}_l$ and Proposition 32 is true for rank $l$.

Now that Proposition 32 is proved for every $l \in [L]$, we can directly deduce Theorem 18 by bounding $|J_l|$ by $|\tilde{J}_{l-1}|^2$.

### C.4 Proof of Proposition 19

Let $l \in [L]$, $j \in \tilde{J}_l$, $o \in \mathcal{O}$. With the same calculation as in the proof of Theorem 18 (see section C.3), we have $\mathbb{E}[p_o^j(w_\infty^j)] = 2^{-2^{l+1}} \rho(S(j))$. Therefore for every $l \in [L]$ the limit layer is an ideal hidden layer with constant $2^{-2^{l+1}}$.

### C.5 Proof of Corollary 20

Suppose Assumption 10 and the assumptions of Theorem 18 hold. Let $\alpha > 0$. Suppose $T/M^{L-1} \ge C_1$ and $M \ge C_2$ where $C_1$ and $C_2$ are the constants defined in Theorem 18, $s_1, \dots, s_L$ are the thresholds given by Theorem 18 and $\tilde{Q}_L$ is non-empty. Then the conclusions of Theorem 18 hold. Let us use the notations introduced in the proof of Theorem 18.

Let $k \in K, j \in \hat{J}_L$. Let us define $S_N^{j \to k} := \sum_{m,o_m^{L+1} \in k} \langle X_{m,t}^{j,L+1} \rangle_{t \in [T]}$ and $\hat{S}_N^{j \to k} := \sum_{m,o_m^{L+1} \in k} \mathbb{E}[X_{m,1}^{j,L+1} | \mathcal{F}_L]$. The variables $(X_{m,t}^{j,L+1})_{1 \le t \le T, m \text{ s.t. } o_m^{L+1} \in k}$ are bounded by 1 and independent knowing $\mathcal{F}_L$. Hence according to Proposition 29, there exists an event $D^{L+1}$ of probability more than $1 - \alpha$ such that on $D^{L+1}$, for every $k \in K, j \in \hat{J}_L$ we have

$$|S_N^{j \to k} - \hat{S}_N^{j \to k}| \le \sqrt{\frac{N^k}{2T} \ln \left( \frac{2|\hat{J}_L||K|}{\alpha} \right)}.$$

Let $(Z_{m,t}^{j,L+1})_{j \in \hat{J}_1 \cup \dots \cup \hat{J}_L, 1 \le m \le M, 1 \le t \le T}$ be the coupled network activity with arbitrary weights $(w_\star^j)_{j \in \hat{J}_1 \cup \dots \cup \hat{J}_L}$ which are $\mathcal{F}_L$-measurable as defined in section 2.2. For $k \in K, j \in \hat{J}_L$ let

$$\bar{S}_N^{j \to k} := \sum_{m,o_m^{L+1} \in k} \mathbb{E}[Z_{m,1}^{j,L+1} | \mathcal{F}_L].$$

Then,

$$|\bar{S}_N^{j \to k} - \hat{S}_N^{j \to k}| \le \sum_{m,o_m^{L+1} \in k} \mathbb{E}[|X_{m,1}^{j,L+1} - Z_{m,1}^{j,L+1}| | \mathcal{F}_L]$$
Hence there exists constants $C_1^l$ and $C_2^l$ such that for $\frac{T}{M^{l-1}} \ge C_1^l$ and $M \ge C_2^l$, (19) is true. Besides, $\frac{T}{M^{l-2}} \ge \frac{T}{M^{l-1}}$ so let us take $C_1^l \ge C_1^{l-1}$ and $C_2^l \ge C_2^{l-1}$ so that we still have $\frac{T}{M^{l-2}} \ge C_1^{l-1}$ and $M \ge C_2^{l-1}$. Under this condition and this choice of threshold, if $j \in \tilde{J}_l$ then $\langle X_{o,t}^{j,l} \rangle_{t \in [T]} \ge s_l$ and otherwise $\langle X_{o,t}^{j,l} \rangle_{t \in [T]} < s_l$ so $\hat{J}_l = \tilde{J}_l$ and Proposition 32 is true for rank $l$.

Now that Proposition 32 is proved for every $l \in [L]$, we can directly deduce Theorem 18 by bounding $|J_l|$ by $|\tilde{J}_{l-1}|^2$.

### C.4 Proof of Proposition 19

Let $l \in [L]$, $j \in \tilde{J}_l$, $o \in \mathcal{O}$. With the same calculation as in the proof of Theorem 18 (see section C.3), we have $\mathbb{E}[p_o^j(w_\infty^j)] = 2^{-2^{l+1}} \rho(S(j))$. Therefore for every $l \in [L]$ the limit layer is an ideal hidden layer with constant $2^{-2^{l+1}}$.

### C.5 Proof of Corollary 20

Suppose Assumption 10 and the assumptions of Theorem 18 hold. Let $\alpha > 0$. Suppose $T/M^{L-1} \ge C_1$ and $M \ge C_2$ where $C_1$ and $C_2$ are the constants defined in Theorem 18, $s_1, \dots, s_L$ are the thresholds given by Theorem 18 and $\tilde{Q}_L$ is non-empty. Then the conclusions of Theorem 18 hold. Let us use the notations introduced in the proof of Theorem 18.

Let $k \in K, j \in \hat{J}_L$. Let us define $S_N^{j \to k} := \sum_{m,o_m^{L+1} \in k} \langle X_{m,t}^{j,L+1} \rangle_{t \in [T]}$ and $\hat{S}_N^{j \to k} := \sum_{m,o_m^{L+1} \in k} \mathbb{E}[X_{m,1}^{j,L+1} | \mathcal{F}_L]$. The variables $(X_{m,t}^{j,L+1})_{1 \le t \le T, m \text{ s.t. } o_m^{L+1} \in k}$ are bounded by 1 and independent knowing $\mathcal{F}_L$. Hence according to Proposition 29, there exists an event $D^{L+1}$ of probability more than $1 - \alpha$ such that on $D^{L+1}$, for every $k \in K, j \in \hat{J}_L$ we have

$$|S_N^{j \to k} - \hat{S}_N^{j \to k}| \le \sqrt{\frac{N^k}{2T} \ln \left( \frac{2|\hat{J}_L||K|}{\alpha} \right)}.$$

Let $(Z_{m,t}^{j,L+1})_{j \in \hat{J}_1 \cup \dots \cup \hat{J}_L, 1 \le m \le M, 1 \le t \le T}$ be the coupled network activity with arbitrary weights $(w_\star^j)_{j \in \hat{J}_1 \cup \dots \cup \hat{J}_L}$ which are $\mathcal{F}_L$-measurable as defined in section 2.2. For $k \in K, j \in \hat{J}_L$ let

$$\bar{S}_N^{j \to k} := \sum_{m,o_m^{L+1} \in k} \mathbb{E}[Z_{m,1}^{j,L+1} | \mathcal{F}_L].$$

Then,

$$|\bar{S}_N^{j \to k} - \hat{S}_N^{j \to k}| \le \sum_{m,o_m^{L+1} \in k} \mathbb{E}[|X_{m,1}^{j,L+1} - Z_{m,1}^{j,L+1}| | \mathcal{F}_L]$$
and similarly as in the proof of Theorem 18 (see section C.3), we have

$$
\begin{align*}
|\bar{S}_N^{j \to k} - \mathring{S}_N^{j \to k}| &\le \sum_{m, o_m^{L+1} \in k} \sum_{l=1}^L \sqrt{|\hat{J}_l|} \max_{a \in \hat{J}_l} \|w_{M+1}^a - w_\star^a\|_2 \\
&= N^k \sum_{l=1}^L \sqrt{|\hat{J}_l|} \max_{a \in \hat{J}_l} \|w_{M+1}^a - w_\star^a\|_2.
\end{align*}
$$

Let us work on $D := D^1 \cap D_{\text{sel}}^1 \cap \dots \cap D^L \cap D_{\text{sel}}^L \cap D^{L+1}$ where for $l \in [L]$, $D^l$ and $D_{\text{sel}}^l$ are the events given in the proof of Theorem 18 (see section C.3). Then $D$ is of probability greater than $1 - 2(L+1)\alpha$. Choose $w_\star = w_\infty$. Then, for $j \in \tilde{J}_L$, $k \in K$,

$$
|S_N^{j \to k} - \bar{S}_N^{j \to k}| \le \sqrt{\frac{N^k}{2T} \ln \left( \frac{2|\tilde{J}_L||K|}{\alpha} \right)} + N^k \sum_{l=1}^L E_w(l). \quad (20)
$$

Here, according to Assumption 13, every nature of object is presented the same
amount of time to the network during the learning phase of the output layer.
Hence Assumption 9 holds for $\xi = \frac{1}{|\mathcal{O}|}$. Therefore, according to Proposition 11,

$$
\mathrm{Disc}_N(w_{1:N}^K) \geq \max_{q^K \in (\mathcal{P}_{\tilde{J}_L})^{|K|}} \mathrm{Disc}_N(q^K) - \frac{C|\mathcal{O}||K|}{|K|-1} \sqrt{\frac{\ln(|\hat{J}_L|)}{N}}.
$$

Let $q^K \in (\mathcal{P}_{\tilde{J}_L})^{|K|}$ be a feasible weight family.

$$
\mathrm{Disc}_N(q^K) = \left\langle \hat{p}_m^k(q^k) - \hat{p}_m^{k'}(q^{k'}) \right\rangle_{\substack{k \in K \\ k' \neq k \\ m, o_m^{L+1} \in k}} = \left\langle (q^k - q^{k'}) \cdot \left( \frac{1}{N^k} S_N^{j \to k} \right)_{j \in \tilde{J}_L} \right\rangle_{k \in K, k' \neq k}.
$$

Besides, according to (21) we have $\mathbb{E}[X_{m,1}^{j,L+1} | \mathcal{F}_L] = 2^{-2^{L+1}} \rho_{o_m^{L+1}}(S(j))$ so

$$
\begin{align*}
\left\langle (q^k - q^{k'}) \cdot \left( \frac{1}{N^k} \bar{S}_N^{j \to k} \right)_{j \in \tilde{J}_L} \right\rangle_{\substack{k \in K \\ k' \neq k \\ o \in k}} &= 2^{-2^{L+1}} \left\langle (q^k - q^{k'}) \cdot \rho_o(S(j)) \right\rangle_{\substack{k \in K \\ k' \neq k \\ o \in k}} \\
&= \gamma_L \mathrm{Disc}^{\mathrm{id}}(q^K)
\end{align*}
$$

with $\gamma_L = 2^{-2^{L+1}}$. Therefore, by lower bounding $N^k$ by $\frac{N}{|\mathcal{O}|}$ for every $k$ we get

$$
\mathrm{Disc}_N(q^K) \geq \gamma_L \mathrm{Disc}^{\mathrm{id}}(q^K) - 2 \sqrt{\frac{|\mathcal{O}|}{2TN} \ln \left( \frac{2|\tilde{J}_L||K|}{\alpha} \right)} - 2 \sum_{l=1}^{L} E_w(l).
$$

Hence

$$
\mathrm{Disc}_N(w_{1:N}^K) \geq \gamma_L \mathrm{Disc}^{\mathrm{id}}(q^K) - 2 \sqrt{\frac{|\mathcal{O}|}{2TN} \ln \left( \frac{2|\tilde{J}_L||K|}{\alpha} \right)} - 2 \sum_{l=1}^{L} E_w(l)
$$
and similarly as in the proof of Theorem 18 (see section C.3), we have

$$
\begin{align*}
|\bar{S}_N^{j \to k} - \mathring{S}_N^{j \to k}| &\le \sum_{m,o_m^{L+1} \in k} \sum_{l=1}^L \sqrt{|\hat{J}_l|} \max_{a \in \hat{J}_l} \|w_{M+1}^a - w_\star^a\|_2 \\
&= N^k \sum_{l=1}^L \sqrt{|\hat{J}_l|} \max_{a \in \hat{J}_l} \|w_{M+1}^a - w_\star^a\|_2.
\end{align*}
$$

Let us work on $D := D^1 \cap D_{\text{sel}}^1 \cap \dots \cap D^L \cap D_{\text{sel}}^L \cap D^{L+1}$ where for $l \in [L]$, $D^l$ and $D_{\text{sel}}^l$ are the events given in the proof of Theorem 18 (see section C.3). Then $D$ is of probability greater than $1 - 2(L+1)\alpha$. Choose $w_\star = w_\infty$. Then, for $j \in \tilde{J}_L$, $k \in K$,

$$
|S_N^{j \to k} - \bar{S}_N^{j \to k}| \le \sqrt{\frac{N^k}{2T} \ln \left( \frac{2|\tilde{J}_L||K|}{\alpha} \right)} + N^k \sum_{l=1}^L E_w(l). \quad (20)
$$

Here, according to Assumption 13, every nature of object is presented the same
amount of time to the network during the learning phase of the output layer.
Hence Assumption 9 holds for $\xi = \frac{1}{|\mathcal{O}|}$. Therefore, according to Proposition 11,

$$
\mathrm{Disc}_N(w_{1:N}^K) \geq \max_{q^K \in (\mathcal{P}_{\tilde{J}_L})^{|K|}} \mathrm{Disc}_N(q^K) - \frac{C|\mathcal{O}||K|}{|K|-1} \sqrt{\frac{\ln(|\hat{J}_L|)}{N}}.
$$

Let $q^K \in (\mathcal{P}_{\tilde{J}_L})^{|K|}$ be a feasible weight family.

$$
\mathrm{Disc}_N(q^K) = \left\langle \hat{p}_m^k(q^k) - \hat{p}_m^{k'}(q^{k'}) \right\rangle_{\substack{k \in K \\ k' \neq k \\ m, o_m^{L+1} \in k}} = \left\langle (q^k - q^{k'}) \cdot \left( \frac{1}{N^k} S_N^{j \to k} \right)_{j \in \tilde{J}_L} \right\rangle_{\substack{k \in K \\ k' \neq k}}.
$$

Besides, according to (21) we have $\mathbb{E}[X_{m,1}^{j,L+1} | \mathcal{F}_L] = 2^{-2^{L+1}} \rho_{o_m^{L+1}}(S(j))$ so

$$
\begin{align*}
\left\langle (q^k - q^{k'}) \cdot \left( \frac{1}{N^k} \bar{S}_N^{j \to k} \right)_{j \in \tilde{J}_L} \right\rangle_{\substack{k \in K \\ k' \neq k \\ o \in k}} &= 2^{-2^{L+1}} \left\langle (q^k - q^{k'}) \cdot \rho_o(S(j)) \right\rangle_{\substack{k \in K \\ k' \neq k \\ o \in k}} \\
&= \gamma_L \mathrm{Disc}^{\mathrm{id}}(q^K)
\end{align*}
$$

with $\gamma_L = 2^{-2^{L+1}}$. Therefore, by lower bounding $N^k$ by $\frac{N}{|\mathcal{O}|}$ for every $k$ we get

$$
\mathrm{Disc}_N(q^K) \geq \gamma_L \mathrm{Disc}^{\mathrm{id}}(q^K) - 2 \sqrt{\frac{|\mathcal{O}|}{2TN} \ln \left( \frac{2|\tilde{J}_L||K|}{\alpha} \right)} - 2 \sum_{l=1}^{L} E_w(l).
$$

Hence

$$
\mathrm{Disc}_N(w_{1:N}^K) \geq \gamma_L \mathrm{Disc}^{\mathrm{id}}(q^K) - 2 \sqrt{\frac{|\mathcal{O}|}{2TN} \ln \left( \frac{2|\tilde{J}_L||K|}{\alpha} \right)} - 2 \sum_{l=1}^{L} E_w(l)
$$
$$ - \frac{C|\mathcal{O}||K|}{|K|-1} \sqrt{\frac{\ln(|\tilde{J}_L|)}{N}}. $$

### C.6 Proof of Theorem 23

Suppose Assumption 10 and the assumptions of Theorem 18 hold. Let $\alpha > 0$. Suppose $T/M^{L-1} \ge C_1$ and $M \ge C_2$ where $C_1$ and $C_2$ are the constants defined in Theorem 18, $s_1, \dots, s_L$ are the thresholds given by Theorem 18 and $\tilde{Q}_L$ is non-empty. Then the conclusions of Theorem 18 hold. For $k \in K$, let $(w_{\infty}^{j \to k})_{j \in \tilde{J}_L} := \frac{1}{|\tilde{J}_L|} \mathbb{1}_{|\tilde{J}_L|}$. Let us work on the event $D$ defined in the proof of Corollary 20 and let us use the notations introduced in section C.5. Then $G_N^{j \to k} = \frac{N}{N^k} S_N^k - \left\langle \frac{N}{N^{k'}} S_N^{k'} \right\rangle_{k' \neq k}$.

Let $\bar{G}_N^{j \to k} = \frac{N}{N^k} \bar{S}_N^k - \left\langle \frac{N}{N^{k'}} \bar{S}_N^{k'} \right\rangle_{k' \neq k}$. Then according to (20),

$$ |G_N^{j \to k} - \bar{G}_N^{j \to k}| \le N \sqrt{\frac{1}{2TN^k} \ln \left( \frac{2|\tilde{J}_L||K|}{\alpha} \right)} + \left\langle N \sqrt{\frac{1}{2TN^{k'}} \ln \left( \frac{2|\tilde{J}_L||K|}{\alpha} \right)} \right\rangle_{k' \neq k} \\ + 2N \sum_{l=1}^{L} E_w(l). $$

Let us study $\bar{G}_N^{j \to k}$. Similarly as in the proof of Theorem 18 (see section C.3),

$$ \mathbb{E}[Z_{m,1}^{j,L+1} | \mathcal{F}_L] = 2^{-2^L+1} \rho_{o_m^{L+1}}(S(j)). \quad (21) $$

Then $\bar{G}_N^{j \to k} = 2^{-2^L+1} \text{Disc}^{j \to k}$. Let $\bar{w}_{N+1}^{j \to k} := \frac{\exp(\eta^k \bar{G}_N^{j \to k})}{\sum_{h \in \tilde{J}_L} \exp(\eta^k \bar{G}_N^{h \to k})}$. Let $k \in K$, $E^k := \arg \max_{j \in \tilde{J}_L} \text{Disc}^{j \to k}$. Then according to Proposition 30, if $E^k = \tilde{J}_L$ then for every $j \in \tilde{J}_L$ we have $\bar{w}_{N+1}^{j \to k} = w_{\infty}^{j \to k}$. Otherwise,

$$ |\bar{w}_{N+1}^{j \to k} - w_{\infty}^{j \to k}| \le E_{\text{EWA}}^k(N, |\tilde{J}_L|) $$

where

$$ E_{\text{EWA}}^k(N, |\tilde{J}_L|) := \frac{1}{|\tilde{J}_L|} \max \left( 1, \frac{|\tilde{J}_L| - |\tilde{J}_L^k|}{|\tilde{J}_L^k|} \right) \exp \left( -2^{-2^L+1} \Delta^k \sqrt{8N \ln(|\tilde{J}_L|)} \right). $$

$$ \text{Let } \xi(N, |\tilde{J}_L|, |O|, T, K) = \sqrt{\frac{\ln(|\tilde{J}_L|)}{|O|T} \ln\left(\frac{2|\tilde{J}_L||K|}{\alpha}\right)} + \frac{1}{|O|} \sqrt{8|\tilde{J}_L| \ln(|\tilde{J}_L|)N} \sum_{l=1}^{L} E_w(l). $$

Besides, according to Proposition 31, with $\eta^k = \frac{1}{|O|} \sqrt{\frac{2 \ln(|\tilde{J}_L|)}{N}}$, by bounding every $\frac{N}{N^{k'}}$ by $|O|$ we get that $\|w_{N+1}^k - \bar{w}_{N+1}^k\|_2 \le \xi(N, |\tilde{J}_L|, |O|, T, K)$. Hence,

$$ \|w_{N+1}^k - w_{\infty}^k\|_2 \le \begin{cases} \xi(N, |\tilde{J}_L|, |O|, T, K) & \text{if } E^k = \tilde{J}_L, \\ \xi(N, |\tilde{J}_L|, |O|, T, K) + \sqrt{|\tilde{J}_L|} E_{\text{EWA}}^k(N, |\tilde{J}_L|) & \text{otherwise.} \end{cases} $$
$$ - \frac{C|\mathcal{O}||K|}{|K|-1} \sqrt{\frac{\ln(|\tilde{J}_L|)}{N}}. $$

### C.6 Proof of Theorem 23

Suppose Assumption 10 and the assumptions of Theorem 18 hold. Let $\alpha > 0$. Suppose $T/M^{L-1} \ge C_1$ and $M \ge C_2$ where $C_1$ and $C_2$ are the constants defined in Theorem 18, $s_1, \dots, s_L$ are the thresholds given by Theorem 18 and $\tilde{Q}_L$ is non-empty. Then the conclusions of Theorem 18 hold. For $k \in K$, let $(w_{\infty}^{j \to k})_{j \in \tilde{J}_L} := \frac{1}{|\tilde{J}_L|} \mathbb{1}_{|\tilde{J}_L|}$. Let us work on the event $D$ defined in the proof of Corollary 20 and let us use the notations introduced in section C.5. Then $G_N^{j \to k} = \frac{N}{N^k} S_N^k - \left\langle \frac{N}{N^{k'}} S_N^{k'} \right\rangle_{k' \neq k}$.

Let $\bar{G}_N^{j \to k} = \frac{N}{N^k} \bar{S}_N^k - \left\langle \frac{N}{N^{k'}} \bar{S}_N^{k'} \right\rangle_{k' \neq k}$. Then according to (20),

$$ |G_N^{j \to k} - \bar{G}_N^{j \to k}| \le N \sqrt{\frac{1}{2TN^k} \ln \left( \frac{2|\tilde{J}_L||K|}{\alpha} \right)} + \left\langle N \sqrt{\frac{1}{2TN^{k'}} \ln \left( \frac{2|\tilde{J}_L||K|}{\alpha} \right)} \right\rangle_{k' \neq k} \\ + 2N \sum_{l=1}^{L} E_w(l). $$

Let us study $\bar{G}_N^{j \to k}$. Similarly as in the proof of Theorem 18 (see section C.3),

$$ \mathbb{E}[Z_{m,1}^{j,L+1} | \mathcal{F}_L] = 2^{-2^L+1} \rho_{o_m^{L+1}}(S(j)). \quad (21) $$

Then $\bar{G}_N^{j \to k} = 2^{-2^L+1} \text{Disc}^{j \to k}$. Let $\bar{w}_{N+1}^{j \to k} := \frac{\exp(\eta^k \bar{G}_N^{j \to k})}{\sum_{h \in \tilde{J}_L} \exp(\eta^k \bar{G}_N^{h \to k})}$. Let $k \in K$, $E^k := \arg \max_{j \in \tilde{J}_L} \text{Disc}^{j \to k}$. Then according to Proposition 30, if $E^k = \tilde{J}_L$ then for every $j \in \tilde{J}_L$ we have $\bar{w}_{N+1}^{j \to k} = w_{\infty}^{j \to k}$. Otherwise,

$$ |\bar{w}_{N+1}^{j \to k} - w_{\infty}^{j \to k}| \le E_{\text{EWA}}^k(N, |\tilde{J}_L|) $$

where

$$ E_{\text{EWA}}^k(N, |\tilde{J}_L|) := \frac{1}{|\tilde{J}_L|} \max \left( 1, \frac{|\tilde{J}_L| - |\tilde{J}_L^k|}{|\tilde{J}_L^k|} \right) \exp \left( -2^{-2^L+1} \Delta^k \sqrt{8N \ln(|\tilde{J}_L|)} \right). $$

$$ \text{Let } \xi(N, |\tilde{J}_L|, |O|, T, K) = \sqrt{\frac{\ln(|\tilde{J}_L|)}{|O|T} \ln\left(\frac{2|\tilde{J}_L||K|}{\alpha}\right)} + \frac{1}{|O|} \sqrt{8|\tilde{J}_L| \ln(|\tilde{J}_L|)N} \sum_{l=1}^{L} E_w(l). $$

Besides, according to Proposition 31, with $\eta^k = \frac{1}{|O|} \sqrt{\frac{2 \ln(|\tilde{J}_L|)}{N}}$, by bounding every $\frac{N}{N^{k'}}$ by $|O|$ we get that $\|w_{N+1}^k - \bar{w}_{N+1}^k\|_2 \le \xi(N, |\tilde{J}_L|, |O|, T, K)$. Hence,

$$ \|w_{N+1}^k - w_{\infty}^k\|_2 \le \begin{cases} \xi(N, |\tilde{J}_L|, |O|, T, K) & \text{if } E^k = \tilde{J}_L, \\ \xi(N, |\tilde{J}_L|, |O|, T, K) + \sqrt{|\tilde{J}_L|} E_{\text{EWA}}^k(N, |\tilde{J}_L|) & \text{otherwise.} \end{cases} $$
### C.7 Proof of Proposition 26

Suppose Assumption 24 (binary correlations) is verified.

Proof of (i) ⇒ (iii). Suppose Assumption 25 (class decomposition) is verified. Let us compute the feature discrepancies of the neurons of $\tilde{J}_L$ in order to compute the weights $w_\infty^K$ given in Theorem 23. For every $k \in K$, we choose the set $E^k$ given in Assumption 25 (class decomposition) with maximal size. Let $j \in \tilde{J}_L$.

$$ \mathrm{Disc}^{j \to k} = \rho^k(S(j)) - \langle \rho^{k'}(S(j)) \rangle_{k' \neq k} = \langle \rho_o(S(j)) \rangle_{o \in k} - \langle \rho_o(S(j)) \rangle_{k' \neq k, o \in k'}. $$

Then according to Assumption 24 (binary correlations), $\rho_o(S(j)) = p$ if and only if $o$ has features $S(j)$, i.e., if and only if $o \in \mathcal{O}^j$, and $\rho_o(S(j)) = 0$ otherwise.

Let $j \in E^k$. Let $o \in k$. We have $\langle \rho_o(S(j)) \rangle_{o \in k} = \frac{|\mathcal{O}^j|}{n^k} p = \frac{C_p}{n^k}$. Let $o \in k' \neq k$. If $\rho_o(S(j)) > 0$, it would mean that $o$ has features $S(j)$ so $o$ would belong to $\mathcal{O}^j$, then $o$ would belong to class $k$. This is impossible so $\rho_o(S(j)) = 0$. Therefore, $\mathrm{Disc}^{j \to k} = \frac{C_p}{n^k}$. Let $j \notin E^k$. This means that there exists $o \in \mathcal{O}^j$ such that $o \notin k$. Therefore $\langle \rho_o(S(j)) \rangle_{o \in k} \le \frac{(C-1)p}{n^k}$ and $\mathrm{Disc}^{j \to k} \le \frac{(C-1)p}{n^k}$. Hence the $\tilde{J}^k = E^k$ (where $\tilde{J}^k$ is the set defined in Theorem 23). So according to Theorem 23, for every $k \in K$ $w_\infty^K = \frac{1}{|E^k|} \mathbb{1}_{j \in E^k}$.

Let $(\tilde{J}_L, (p_o^j)_{o \in \mathcal{O}, j \in \tilde{J}_L})$ an ideal hidden layer. Let $\gamma_L$ its constant. Let $k \in K$, $o \in \mathcal{O}$. The spiking probability $p_o^k$ of neuron $k$ when presented with object $o$ is

$$ p_o^k = w_\infty^k \cdot p_o^{\tilde{J}_L} = \gamma_L w_\infty^k \cdot (\rho_o(S(j)))_{j \in \tilde{J}_L} = \frac{\gamma_L}{|E^k|} \sum_{j \in E^k} \rho_o(S(j)) = \frac{p \gamma_L n_o^j}{|E^k|}, $$

where $n_o^j$ is the amount of sets $\mathcal{O}^j$ containing $o$. If $o \in k$, according to Assumption 25 (class decomposition) $n_o^j \ge 1$. If $o \notin k$ then $n_o^j = 0$ (otherwise $o$ would belong to a set $\mathcal{O}^j$ in the composition of class $k$ so $o$ would belong to $k$). Therefore, $p_o^k > 0$ if, and only if, $o \in k$ so $w_\infty^K$ is a strong feasible weight family for the ideal layer $\tilde{J}_L$.

Proof of (ii) ⇒ (i). Suppose there exists a strong feasible weight family $q^K$ w.r.t. $\tilde{J}_L$. Let $k \in K$ and $E^k := \{j \in \tilde{J}_L, q^{j \to k} > 0\}$. Let us show that $k = \bigcup_{j \in E^k} \mathcal{O}^j$. The ideal spiking probability of neuron $k$ when presented with $o \in \mathcal{O}$ is $p_o^{k,id} = \sum_{j \in \tilde{J}_L} q^{j \to k} \rho_o(S(j))$. Let $o \in k$. Then $p_o^{k,id} > 0$ so there exists $j \in \tilde{J}_L$ such that $q^{j \to k} > 0$ and $\rho_o(S(j)) > 0$. Hence $j \in E^k$ and $o$ has features $S(j)$ so $o \in \mathcal{O}^j$. Therefore $k \subset \bigcup_{j \in E^k} \mathcal{O}^j$. Let $o \in \bigcup_{j \in E^k} \mathcal{O}^j$. There exists $j \in E^k$ such that $o \in \mathcal{O}^j$ and $q^{j \to k} > 0$. Then $p_o^{k,id} > 0$ so $o \in k$. Therefore, $\bigcup_{j \in E^k} \mathcal{O}^j \subset k$. It is obvious that (iii) ⇒ (ii) so we can conclude.

### C.8 Proof of Proposition 27

Let $j \in J_L$. Let $o^j := (o^{i \to j})_{i \in I}$ where $o^{i \to j} = 1$ if and only if $i \in S(j)$. Then $j$ is the only neuron of layer $J_L$ activated by $o^j$. Indeed, all the sets $S(j')$ for
### C.7 Proof of Proposition 26

Suppose Assumption 24 (binary correlations) is verified.

Proof of (i) ⇒ (iii). Suppose Assumption 25 (class decomposition) is verified. Let us compute the feature discrepancies of the neurons of $\tilde{J}_L$ in order to compute the weights $w_\infty^K$ given in Theorem 23. For every $k \in K$, we choose the set $E^k$ given in Assumption 25 (class decomposition) with maximal size. Let $j \in \tilde{J}_L$.

$$ \mathrm{Disc}^{j \to k} = \rho^k(S(j)) - \langle \rho^{k'}(S(j)) \rangle_{k' \neq k} = \langle \rho_o(S(j)) \rangle_{o \in k} - \langle \rho_o(S(j)) \rangle_{k' \neq k, o \in k'}. $$

Then according to Assumption 24 (binary correlations), $\rho_o(S(j)) = p$ if and only if $o$ has features $S(j)$, i.e., if and only if $o \in \mathcal{O}^j$, and $\rho_o(S(j)) = 0$ otherwise.

Let $j \in E^k$. Let $o \in k$. We have $\langle \rho_o(S(j)) \rangle_{o \in k} = \frac{|\mathcal{O}^j|}{n^k} p = \frac{C_p}{n^k}$. Let $o \in k' \neq k$. If $\rho_o(S(j)) > 0$, it would mean that $o$ has features $S(j)$ so $o$ would belong to $\mathcal{O}^j$, then $o$ would belong to class $k$. This is impossible so $\rho_o(S(j)) = 0$. Therefore, $\mathrm{Disc}^{j \to k} = \frac{C_p}{n^k}$. Let $j \notin E^k$. This means that there exists $o \in \mathcal{O}^j$ such that $o \notin k$. Therefore $\langle \rho_o(S(j)) \rangle_{o \in k} \le \frac{(C-1)p}{n^k}$ and $\mathrm{Disc}^{j \to k} \le \frac{(C-1)p}{n^k}$. Hence the $\tilde{J}^k = E^k$ (where $\tilde{J}^k$ is the set defined in Theorem 23). So according to Theorem 23, for every $k \in K$ $w_\infty^K = \frac{1}{|E^k|} \mathbb{1}_{j \in E^k}$.

Let $(\tilde{J}_L, (p_o^j)_{o \in \mathcal{O}, j \in \tilde{J}_L})$ an ideal hidden layer. Let $\gamma_L$ its constant. Let $k \in K$, $o \in \mathcal{O}$. The spiking probability $p_o^k$ of neuron $k$ when presented with object $o$ is

$$ p_o^k = w_\infty^k \cdot p_o^{\tilde{J}_L} = \gamma_L w_\infty^k \cdot (\rho_o(S(j)))_{j \in \tilde{J}_L} = \frac{\gamma_L}{|E^k|} \sum_{j \in E^k} \rho_o(S(j)) = \frac{p \gamma_L n_o^j}{|E^k|}, $$

where $n_o^j$ is the amount of sets $\mathcal{O}^j$ containing $o$. If $o \in k$, according to Assumption 25 (class decomposition) $n_o^j \ge 1$. If $o \notin k$ then $n_o^j = 0$ (otherwise $o$ would belong to a set $\mathcal{O}^j$ in the composition of class $k$ so $o$ would belong to $k$). Therefore, $p_o^k > 0$ if, and only if, $o \in k$ so $w_\infty^K$ is a strong feasible weight family for the ideal layer $\tilde{J}_L$.

Proof of (ii) ⇒ (i). Suppose there exists a strong feasible weight family $q^K$ w.r.t. $\tilde{J}_L$. Let $k \in K$ and $E^k := \{j \in \tilde{J}_L, q^{j \to k} > 0\}$. Let us show that $k = \bigcup_{j \in E^k} \mathcal{O}^j$. The ideal spiking probability of neuron $k$ when presented with $o \in \mathcal{O}$ is $p_o^{k,id} = \sum_{j \in \tilde{J}_L} q^{j \to k} \rho_o(S(j))$. Let $o \in k$. Then $p_o^{k,id} > 0$ so there exists $j \in \tilde{J}_L$ such that $q^{j \to k} > 0$ and $\rho_o(S(j)) > 0$. Hence $j \in E^k$ and $o$ has features $S(j)$ so $o \in \mathcal{O}^j$. Therefore $k \subset \bigcup_{j \in E^k} \mathcal{O}^j$. Let $o \in \bigcup_{j \in E^k} \mathcal{O}^j$. There exists $j \in E^k$ such that $o \in \mathcal{O}^j$ and $q^{j \to k} > 0$. Then $p_o^{k,id} > 0$ so $o \in k$. Therefore, $\bigcup_{j \in E^k} \mathcal{O}^j \subset k$. It is obvious that (iii) ⇒ (ii) so we can conclude.

### C.8 Proof of Proposition 27

Let $j \in J_L$. Let $o^j := (o^{i \to j})_{i \in I}$ where $o^{i \to j} = 1$ if and only if $i \in S(j)$. Then $j$ is the only neuron of layer $J_L$ activated by $o^j$. Indeed, all the sets $S(j')$ for
$j' \in J_L$ have the same size and only a neuron $j'$ with smaller $|S(j')|$ can also be activated by $o^j$. Let $S := \{o_j, j \in J_L\}$. Then $|S| = |J_L|$ because all the $o^j$ are distinct. This set can be fully shattered by $H$: indeed, let $S' \subset S$, and $J'_L := \{j \in J_L, \exists o \in S', o = o^j\}$. Then $S'$ and $S \setminus S'$ are separated by $\mathbb{1}_{J'_L}$.

Let $S$ be a set of objects that can be fully shattered by $H$. In particular, for each $o \in S$, there exists $J'_L \subset J_L$ non empty such that such that $o$ is the unique object in $S$ which activates a neuron in $J'_L$. Let $j_o$ be such a neuron. Then $o \mapsto j_o$ is an injection so $|S| \le |J_L|$.

### C.9 Proof of proposition 28

Let us use the notations of Theorem 23. Let $j \in \tilde{J}_L, k \in K$. The limit cumulative gain in $M$ and $T$ of a hidden neuron is of the form

$$ \bar{G}_{N}^{j \to k} := CN \left( \langle p_{o,\infty}^{j} \rangle_{o \in k} - \langle p_{o,\infty}^{j} \rangle_{k' / k' \neq k} \right) $$

where $C > 0$ is a constant and $p_{o,\infty}^j$ is the limit spiking probability of hidden neuron $j$ when presented with object of nature $o$. Since limit hidden layers are not ideal layers, another quantity replaces the feature discrepancy: the quantity

$$ c^{j \to k} := \langle p_{o,\infty}^{j} \rangle_{o \in k} - \langle p_{o,\infty}^{j} \rangle_{k' / k' \neq k} $$

and according to Proposition 30, the output weights of neuron $k \in K$ converge to uniform distribution of weight on the set $\arg\max_{j \in \tilde{J}_L} c^{j \to k}$. In order to compute the limit weights of neuron $k_2$, let us compute the quantities $c^{j \to k_2}$. Let $m \in [N]$. The limit conditional spiking probability of a hidden neuron $j = i_1 \lor i_2$ is $(-\nu + \frac{1}{2}(X_{m,t}^{i_1} + X_{m,t}^{i_2}))_+$. Therefore, when only one of the two input neurons $i_1$ and $i_2$ is active, the spiking probability of $j$ is $q := (\frac{1}{2} - \nu)p'$ and when the two neurons $i_2$ and $i_2$ are active, the spiking probability of $j$ is $p := p'^2(1-\nu) + 2p'(1-p')(\frac{1}{2} - \nu)$. By definition of the feature discrepancy we have

$$ d^{\text{Blue} \lor \text{Square} \to k_2} = \frac{1}{5}p - q $$

$$ d^{\text{Red} \lor \text{Circle} \to k_2} = \frac{1}{5}p + \frac{2}{5}q - \frac{1}{2}q = \frac{1}{5}p - \frac{1}{10}q $$

$$ d^{\text{Blue} \lor \text{Circle} \to k_2} = \frac{3}{5}q - \frac{1}{4}p - \frac{1}{4}q = \frac{7}{20}q - \frac{1}{4}p $$

By symmetry, we know every $d^{i \to k_2}$. Since $\nu < \frac{1}{2}$ we have $q > 0$. Then $d^{\text{Blue} \lor \text{Square} \to k_2} < d^{\text{Red} \lor \text{Circle} \to k_2}$. Besides, $d^{\text{Red} \lor \text{Circle} \to k_2} - d^{\text{Blue} \lor \text{Circle} \to k_2} = \frac{9}{20}p - \frac{9}{20}q > 0$, because $p > q$. Therefore, the limit weights of $k_2$ converge to the family
$j' \in J_L$ have the same size and only a neuron $j'$ with smaller $|S(j')|$ can also be activated by $o^j$. Let $S := \{o_j, j \in J_L\}$. Then $|S| = |J_L|$ because all the $o^j$ are distinct. This set can be fully shattered by $H$: indeed, let $S' \subset S$, and $J'_L := \{j \in J_L, \exists o \in S', o = o^j\}$. Then $S'$ and $S \setminus S'$ are separated by $\mathbb{1}_{J'_L}$.

Let $S$ be a set of objects that can be fully shattered by $H$. In particular, for each $o \in S$, there exists $J'_L \subset J_L$ non empty such that such that $o$ is the unique object in $S$ which activates a neuron in $J'_L$. Let $j_o$ be such a neuron. Then $o \mapsto j_o$ is an injection so $|S| \le |J_L|$.

### C.9 Proof of proposition 28

Let us use the notations of Theorem 23. Let $j \in \tilde{J}_L, k \in K$. The limit cumulative gain in $M$ and $T$ of a hidden neuron is of the form

$$ \bar{G}_{N}^{j \to k} := CN \left( \langle p_{o,\infty}^{j} \rangle_{o \in k} - \langle p_{o,\infty}^{j} \rangle_{k' / k' \neq k} \right) $$

where $C > 0$ is a constant and $p_{o,\infty}^j$ is the limit spiking probability of hidden neuron $j$ when presented with object of nature $o$. Since limit hidden layers are not ideal layers, another quantity replaces the feature discrepancy: the quantity

$$ c^{j \to k} := \langle p_{o,\infty}^{j} \rangle_{o \in k} - \langle p_{o,\infty}^{j} \rangle_{k' / k' \neq k} $$

and according to Proposition 30, the output weights of neuron $k \in K$ converge to uniform distribution of weight on the set $\arg\max_{j \in \tilde{J}_L} c^{j \to k}$. In order to compute the limit weights of neuron $k_2$, let us compute the quantities $c^{j \to k_2}$. Let $m \in [N]$. The limit conditional spiking probability of a hidden neuron $j = i_1 \lor i_2$ is $(-\nu + \frac{1}{2}(X_{m,t}^{i_1} + X_{m,t}^{i_2}))_+$. Therefore, when only one of the two input neurons $i_1$ and $i_2$ is active, the spiking probability of $j$ is $q := (\frac{1}{2} - \nu)p'$ and when the two neurons $i_2$ and $i_2$ are active, the spiking probability of $j$ is $p := p'^2(1-\nu) + 2p'(1-p')(\frac{1}{2} - \nu)$. By definition of the feature discrepancy we have

$$ d^{\text{Blue} \lor \text{Square} \to k_2} = \frac{1}{5}p - q $$

$$ d^{\text{Red} \lor \text{Circle} \to k_2} = \frac{1}{5}p + \frac{2}{5}q - \frac{1}{2}q = \frac{1}{5}p - \frac{1}{10}q $$

$$ d^{\text{Blue} \lor \text{Circle} \to k_2} = \frac{3}{5}q - \frac{1}{4}p - \frac{1}{4}q = \frac{7}{20}q - \frac{1}{4}p $$

By symmetry, we know every $d^{i \to k_2}$. Since $\nu < \frac{1}{2}$ we have $q > 0$. Then $d^{\text{Blue} \lor \text{Square} \to k_2} < d^{\text{Red} \lor \text{Circle} \to k_2}$. Besides, $d^{\text{Red} \lor \text{Circle} \to k_2} - d^{\text{Blue} \lor \text{Circle} \to k_2} = \frac{9}{20}p - \frac{9}{20}q > 0$, because $p > q$. Therefore, the limit weights of $k_2$ converge to the family
putting weight 1/4 on Red∩Circle, Red∩Triangle, Green∩Circle and Green∩Triangle.
Hence, the limit activity of $k_2$ is equal to zero when presented with □, so this
objects is not well classified.

References

Macrene R Alexiades and Constance L Cepko. Subsets of retinal progenitors display temporally regulated and distinct biases in the fates of their progeny. *Development*, 124(6):1119–1131, 1997.

Emmanuel Bacry, Iacopo Mastromatteo, and Jean-François Muzy. Hawkes processes in finance. *Market Microstructure and Liquidity*, 1(01):1550005, 2015.

Emmanuel Bacry, Martin Bompaire, Philip Deegan, Stéphane Gaïffas, and Søren V Poulsen. tick: A python library for statistical learning, with an emphasis on hawkes processes and time-dependent models. *JMLR*, 18(1):7937–7941, 2017.

Yujia Bao, Zhaobin Kuang, Peggy Peissig, David Page, and Rebecca Willett. Hawkes process modeling of adverse drug reactions with longitudinal observational data. In *Proceedings of the 2nd Machine Learning for Healthcare Conference*, volume 68, pages 177–190, 2017.

Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou. Birth of a transformer: A memory viewpoint. In *NeurIPS*, 2023.

Pierre Brémaud and Laurent Massoulié. Stability of nonlinear hawkes processes. *Ann. Prob.*, pages 1563–1588, 1996.

Natalia Caporale and Yang Dan. Spike timing-dependent plasticity: a hebbian learning rule. *Annu. Rev. Neurosci.*, 31:25–46, 2008.

Nicolo Cesa-Bianchi and Gábor Lugosi. *Prediction, learning, and games*. Cambridge university press, 2006.

Wen-Hao Chiang and George Mohler. Hawkes process multi-armed bandits for disaster search and rescue. *arXiv preprint arXiv:2004.01580*, 2020.

Jean-Baptiste Cordonnier, Andreas Loukas, and Martin Jaggi. On the relationship between self-attention and convolutional layers. In *ICLR*, 2020.

Kunihiko Fukushima and Sei Miyake. Neocognitron: A new algorithm for pattern recognition tolerant of deformations and shifts in position. *Pattern Recognit.*, 15(6):455–469, 1982.

Antonio Galves and Eva Löcherbach. Modeling networks of spiking neurons as interacting processes with memory of variable length. *J. Soci. Fr. Stat.*, 157(1): 17–32, 2016.
putting weight 1/4 on Red∩Circle, Red∩Triangle, Green∩Circle and Green∩Triangle.
Hence, the limit activity of $k_2$ is equal to zero when presented with □, so this
objects is not well classified.

References

Macrene R Alexiades and Constance L Cepko. Subsets of retinal progenitors display temporally regulated and distinct biases in the fates of their progeny. *Development*, 124(6):1119-1131, 1997.

Emmanuel Bacry, Iacopo Mastromatteo, and Jean-François Muzy. Hawkes processes in finance. *Market Microstructure and Liquidity*, 1(01):1550005, 2015.

Emmanuel Bacry, Martin Bompaire, Philip Deegan, Stéphane Gaïffas, and Søren V Poulsen. tick: A python library for statistical learning, with an emphasis on hawkes processes and time-dependent models. *JMLR*, 18(1):7937-7941, 2017.

Yujia Bao, Zhaobin Kuang, Peggy Peissig, David Page, and Rebecca Willett. Hawkes process modeling of adverse drug reactions with longitudinal observational data. In *Proceedings of the 2nd Machine Learning for Healthcare Conference*, volume 68, pages 177-190, 2017.

Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou. Birth of a transformer: A memory viewpoint. In *NeurIPS*, 2023.

Pierre Brémaud and Laurent Massoulié. Stability of nonlinear hawkes processes. *Ann. Prob.*, pages 1563-1588, 1996.

Natalia Caporale and Yang Dan. Spike timing-dependent plasticity: a hebbian learning rule. *Annu. Rev. Neurosci.*, 31:25-46, 2008.

Nicolo Cesa-Bianchi and Gábor Lugosi. *Prediction, learning, and games*. Cambridge university press, 2006.

Wen-Hao Chiang and George Mohler. Hawkes process multi-armed bandits for disaster search and rescue. *arXiv preprint arXiv:2004.01580*, 2020.

Jean-Baptiste Cordonnier, Andreas Loukas, and Martin Jaggi. On the relationship between self-attention and convolutional layers. In *ICLR*, 2020.

Kunihiko Fukushima and Sei Miyake. Neocognitron: A new algorithm for pattern recognition tolerant of deformations and shifts in position. *Pattern Recognit.*, 15(6):455-469, 1982.

Antonio Galves and Eva Löcherbach. Modeling networks of spiking neurons as interacting processes with memory of variable length. *J. Soci. Fr. Stat.*, 157(1): 17-32, 2016.
Bolin Gao and Lacra Pavel. On the properties of the softmax function with
application in game theory and reinforcement learning, 2018.

Felipe Gerhard, Moritz Deger, and Wilson Truccolo. On the stability and dynamics of stochastic spiking neuron models: Nonlinear hawkes process and point process glms. *PLoS computational biology*, 13(2):e1005390, 2017.

G.L. Gerstein, P. Bedenbaugh, and A.M.H.J. Aertsen. Neuronal assemblies. *IEEE Trans. Biomed. Eng.*, 36(1):4–14, 1989. doi: 10.1109/10.16444.

Mark A Gluck and Gordon H Bower. From conditioning to category learning: an adaptive network model. *J. Exp. Psychol.*, 117(3):227, 1988.

Eric C Hall and Rebecca M Willett. Tracking dynamic point processes on networks. *IEEE Trans. Inf. Theory*, 62(7):4327–4346, 2016.

Alan G Hawkes. Spectra of some self-exciting and mutually exciting point processes. *Biometrika*, 58(1):83–90, 1971.

Alan G Hawkes. Hawkes processes and their applications to finance: a review. *Quantitative Finance*, 18(2):193–198, 2018.

Donald Olding Hebb. *The organization of behavior: A neuropsychological theory*. Psychology press, 2005.

Pierre Hodara and Eva Löcherbach. Hawkes processes with variable length memory and an infinite number of components. *Adv. Appl. Probab.*, 49(1):84–107, 2017.

David H Hubel and Torsten N Wiesel. Receptive fields, binocular interaction and functional architecture in the cat's visual cortex. *J. Physiol.*, 160(1):106, 1962.

Sophie Jaffard, Samuel Vaiter, Alexandre Muzy, and Patricia Reynaud-Bouret. Provable local learning rule by expert aggregation for a Hawkes network. In *AISTATS*, 2024.

Matthias Kirchner. An estimation procedure for the hawkes process. *Quantitative Finance*, 17(4):571–595, 2017.

John K Kruschke. Alcove: An exemplar-based connectionist model of category learning. In *Connectionist psychology: a text with readings*, pages 107–138. Psychology Press, 2020.

Regis C Lambert, Christine Tuleau-Malot, Thomas Bessaih, Vincent Rivoirard, Yann Bouret, Nathalie Leresche, and Patricia Reynaud-Bouret. Reconstructing the functional connectivity of multiple spike trains using hawkes models. *J. Neurosci. Methods*, 297:9–21, 2018.
Bolin Gao and Lacra Pavel. On the properties of the softmax function with
application in game theory and reinforcement learning, 2018.

Felipe Gerhard, Moritz Deger, and Wilson Truccolo. On the stability and dynamics of stochastic spiking neuron models: Nonlinear hawkes process and point process glms. *PLoS computational biology*, 13(2):e1005390, 2017.

G.L. Gerstein, P. Bedenbaugh, and A.M.H.J. Aertsen. Neuronal assemblies. *IEEE Trans. Biomed. Eng.*, 36(1):4–14, 1989. doi: 10.1109/10.16444.

Mark A Gluck and Gordon H Bower. From conditioning to category learning: an adaptive network model. *J. Exp. Psychol.*, 117(3):227, 1988.

Eric C Hall and Rebecca M Willett. Tracking dynamic point processes on networks. *IEEE Trans. Inf. Theory*, 62(7):4327–4346, 2016.

Alan G Hawkes. Spectra of some self-exciting and mutually exciting point processes. *Biometrika*, 58(1):83–90, 1971.

Alan G Hawkes. Hawkes processes and their applications to finance: a review. *Quantitative Finance*, 18(2):193–198, 2018.

Donald Olding Hebb. *The organization of behavior: A neuropsychological theory*. Psychology press, 2005.

Pierre Hodara and Eva Löcherbach. Hawkes processes with variable length memory and an infinite number of components. *Adv. Appl. Probab.*, 49(1):84–107, 2017.

David H Hubel and Torsten N Wiesel. Receptive fields, binocular interaction and functional architecture in the cat's visual cortex. *J. Physiol.*, 160(1):106, 1962.

Sophie Jaffard, Samuel Vaiter, Alexandre Muzy, and Patricia Reynaud-Bouret. Provable local learning rule by expert aggregation for a Hawkes network. In *AISTATS*, 2024.

Matthias Kirchner. An estimation procedure for the hawkes process. *Quantitative Finance*, 17(4):571–595, 2017.

John K Kruschke. Alcove: An exemplar-based connectionist model of category learning. In *Connectionist psychology: a text with readings*, pages 107–138. Psychology Press, 2020.

Regis C Lambert, Christine Tuleau-Malot, Thomas Bessaih, Vincent Rivoirard, Yann Bouret, Nathalie Leresche, and Patricia Reynaud-Bouret. Reconstructing the functional connectivity of multiple spike trains using hawkes models. *J. Neurosci. Methods*, 297:9–21, 2018.
Yann LeCun, Bernhard Boser, John Denker, Donnie Henderson, Richard Howard, Wayne Hubbard, and Lawrence Jackel. Handwritten digit recognition with a back-propagation network. In *NeurIPS*, 1989.

Robert Legenstein, Christian Naeger, and Wolfgang Maass. What can a neuron learn with spike-timing-dependent plasticity? *Neural Comput.*, 17(11):2337-2382, 2005.

Robert Legenstein, Dejan Pecevski, and Wolfgang Maass. A learning theory for reward-modulated spike-timing-dependent plasticity with application to biofeedback. *PLoS computational biology*, 4(10):e1000180, 2008.

Ashok Litwin-Kumar and Brent Doiron. Formation and maintenance of neuronal assemblies through synaptic plasticity. *Nature communications*, 5(1):5319, 2014.

C. Mascart, D. Hill, A. Muzy, and P. Reynaud-Bouret. Scalability of large neural network simulations via activity tracking with time asynchrony and procedural connectivity. *Neural Comput.*, 34(9):1915-1943, 2022.

Cyrille Mascart, David Hill, Alexandre Muzy, and Patricia Reynaud-Bouret. Efficient simulation of sparse graphs of point processes. *ACM Transactions on Modeling and Computer Simulation*, 33(1-2):1-27, 2023.

Giulia Mezzadri, Thomas Laloë, Fabien Mathy, and Patricia Reynaud-Bouret. Hold-out strategy for selecting learning models: Application to categorization subjected to presentation orders. *J. Math. Psychol.*, 109:102691, 2022.

Guilherme Ost and Patricia Reynaud-Bouret. Sparse space-time models: Concentration inequalities and lasso. 2020.

Tien Cuong Phi, Alexandre Muzy, and Patricia Reynaud-Bouret. Event-scheduling algorithms with kalikow decomposition for simulating potentially infinite neuronal networks. *SN Comput. Sci.*, 1(1):1-10, 2020.

Brian G Rash and Elizabeth A Grove. Area and layer patterning in the developing cerebral cortex. *Current opinion in neurobiology*, 16(1):25-34, 2006.

Patricia Reynaud-Bouret and Sophie Schbath. Adaptive estimation for hawkes processes; application to genome analysis. 2010.

Patricia Reynaud-Bouret, Vincent Rivoirard, and Christine Tuleau-Malot. Inference of functional connectivity in neurosciences via hawkes processes. In *GlobalSIP*, pages 317-320, 2013.

Raanan Y. Rohekar, Yaniv Gurwicz, and Shami Nisimov. Causal interpretation of self-attention in pre-trained transformers. In *NeurIPS*, 2023.
Yann LeCun, Bernhard Boser, John Denker, Donnie Henderson, Richard Howard, Wayne Hubbard, and Lawrence Jackel. Handwritten digit recognition with a back-propagation network. In *NeurIPS*, 1989.

Robert Legenstein, Christian Naeger, and Wolfgang Maass. What can a neuron learn with spike-timing-dependent plasticity? *Neural Comput.*, 17(11):2337-2382, 2005.

Robert Legenstein, Dejan Pecevski, and Wolfgang Maass. A learning theory for reward-modulated spike-timing-dependent plasticity with application to biofeedback. *PLoS computational biology*, 4(10):e1000180, 2008.

Ashok Litwin-Kumar and Brent Doiron. Formation and maintenance of neuronal assemblies through synaptic plasticity. *Nature communications*, 5(1):5319, 2014.

C. Mascart, D. Hill, A. Muzy, and P. Reynaud-Bouret. Scalability of large neural network simulations via activity tracking with time asynchrony and procedural connectivity. *Neural Comput.*, 34(9):1915-1943, 2022.

Cyrille Mascart, David Hill, Alexandre Muzy, and Patricia Reynaud-Bouret. Efficient simulation of sparse graphs of point processes. *ACM Transactions on Modeling and Computer Simulation*, 33(1-2):1-27, 2023.

Giulia Mezzadri, Thomas Laloë, Fabien Mathy, and Patricia Reynaud-Bouret. Hold-out strategy for selecting learning models: Application to categorization subjected to presentation orders. *J. Math. Psychol.*, 109:102691, 2022.

Guilherme Ost and Patricia Reynaud-Bouret. Sparse space-time models: Concentration inequalities and lasso. 2020.

Tien Cuong Phi, Alexandre Muzy, and Patricia Reynaud-Bouret. Event-scheduling algorithms with kalikow decomposition for simulating potentially infinite neural networks. *SN Comput. Sci.*, 1(1):1-10, 2020.

Brian G Rash and Elizabeth A Grove. Area and layer patterning in the developing cerebral cortex. *Current opinion in neurobiology*, 16(1):25-34, 2006.

Patricia Reynaud-Bouret and Sophie Schbath. Adaptive estimation for hawkes processes; application to genome analysis. 2010.

Patricia Reynaud-Bouret, Vincent Rivoirard, and Christine Tuleau-Malot. Inference of functional connectivity in neurosciences via hawkes processes. In *GlobalSIP*, pages 317-320, 2013.

Raanan Y. Rohekar, Yaniv Gurwicz, and Shami Nisimov. Causal interpretation of self-attention in pre-trained transformers. In *NeurIPS*, 2023.
F. Rosenblatt. *The Perceptron, a Perceiving and Recognizing Automaton Project Para*. Cornell Aeronautical Laboratory, 1957.

Frank Rosenblatt et al. *Principles of neurodynamics: Perceptrons and the theory of brain mechanisms*, volume 55. Spartan books Washington, DC, 1962.

Roman Rybka, Yury Davydov, Danila Vlasov, Alexey Serenko, Alexander Sboev, and Vyacheslav Ilyin. Comparison of bagging and sparsity methods for connectivity reduction in spiking neural networks with memristive plasticity. *Big Data and Cognitive Computing*, 8(3):22, 2024.

Alexander Sboev, Yury Davydov, Roman Rybka, Danila Vlasov, and Alexey Serenko. A comparison of two variants of memristive plasticity for solving the classification problem of handwritten digits recognition. In *Biologically Inspired Cognitive Architectures 2021*, pages 438-446, 2022.

Menahem Segal. Dendritic spines and long-term plasticity. *Nature Reviews Neuroscience*, 6(4):277-284, 2005.

Wolf Singer, Andreas K Engel, Andreas K Kreiter, Matthias HJ Munk, Sergio Neuenschwander, and Pieter R Roelfsema. Neuronal assemblies: necessity, signature and detectability. *Trends in cognitive sciences*, 1(7):252-261, 1997.

James V Stone. Principles of neural information theory. *Computational Neuroscience and Metabolic Efficiency*, 2018.

Amirhossein Tavanaei, Masoud Ghodrati, Saeed Reza Kheradpisheh, Timothée Masquelier, and Anthony Maida. Deep learning in spiking neural networks. *Neural Netw.*, 111:47-63, 2019.

K Türkyilmaz, Maria Nicolette Margaretha van Lieshout, and A Stein. Comparing the hawkes and trigger process models for aftershock sequences following the 2005 kashmir earthquake. *Mathematical geosciences*, 45:149-164, 2013.

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. *NeurIPS*, 2017.

Ke Zhou, Hongyuan Zha, and Le Song. Learning social infectivity in sparse low-rank networks using multi-dimensional hawkes processes. In *AISTATS*, 2013.

Simiao Zuo, Haoming Jiang, Zichong Li, Tuo Zhao, and Hongyuan Zha. Transformer Hawkes process. In *ICML*, 2020.
F. Rosenblatt. *The Perceptron, a Perceiving and Recognizing Automaton Project Para*. Cornell Aeronautical Laboratory, 1957.

Frank Rosenblatt et al. *Principles of neurodynamics: Perceptrons and the theory of brain mechanisms*, volume 55. Spartan books Washington, DC, 1962.

Roman Rybka, Yury Davydov, Danila Vlasov, Alexey Serenko, Alexander Sboev, and Vyacheslav Ilyin. Comparison of bagging and sparsity methods for connectivity reduction in spiking neural networks with memristive plasticity. *Big Data and Cognitive Computing*, 8(3):22, 2024.

Alexander Sboev, Yury Davydov, Roman Rybka, Danila Vlasov, and Alexey Serenko. A comparison of two variants of memristive plasticity for solving the classification problem of handwritten digits recognition. In *Biologically Inspired Cognitive Architectures 2021*, pages 438-446, 2022.

Menahem Segal. Dendritic spines and long-term plasticity. *Nature Reviews Neuroscience*, 6(4):277-284, 2005.

Wolf Singer, Andreas K Engel, Andreas K Kreiter, Matthias HJ Munk, Sergio Neuenschwander, and Pieter R Roelfsema. Neuronal assemblies: necessity, signature and detectability. *Trends in cognitive sciences*, 1(7):252-261, 1997.

James V Stone. Principles of neural information theory. *Computational Neuroscience and Metabolic Efficiency*, 2018.

Amirhossein Tavanaei, Masoud Ghodrati, Saeed Reza Kheradpisheh, Timothée Masquelier, and Anthony Maida. Deep learning in spiking neural networks. *Neural Netw.*, 111:47-63, 2019.

K Türkyilmaz, Maria Nicolette Margaretha van Lieshout, and A Stein. Comparing the hawkes and trigger process models for aftershock sequences following the 2005 kashmir earthquake. *Mathematical geosciences*, 45:149-164, 2013.

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. *NeurIPS*, 2017.

Ke Zhou, Hongyuan Zha, and Le Song. Learning social infectivity in sparse low-rank networks using multi-dimensional hawkes processes. In *AISTATS*, 2013.

Simiao Zuo, Haoming Jiang, Zichong Li, Tuo Zhao, and Hongyuan Zha. Transformer Hawkes process. In *ICML*, 2020.