where $D_{n/q} = \frac{RM\sqrt{q}}{\sqrt{n}} (k\sqrt{d\log(k)} + \sqrt{x})$.

The proof of Lemma 11 is postponed to Section 7.2.3. Equipped with Lemma 11, we first prove recursively that, if $\mathbf{c}^{(0)} \in \mathcal{B}(\mathbf{c}^*, R_0)$, then w.h.p., for all $t > 0$ $\mathbf{c}^{(t)} \in \mathcal{B}(\mathbf{c}^*, R_0)$. We let $\Omega_1$ be defined as

$$ \Omega_1 = \left\{ C_2 k R^2 M^2 \left( \frac{1}{n} \sum_{i=1}^{n} 1_{X_i \neq \tilde{X}_i} \right)^2 / p_{\min}^2 \le R_0^2/8 \right\}. $$

Noting that $\mathbb{E} \left( \frac{1}{n} \sum_{i=1}^{n} 1_{X_i \neq \tilde{X}_i} \right)^2 \le \mathbb{E} \left( \frac{1}{n} \sum_{i=1}^{n} 1_{X_i \neq \tilde{X}_i} \right) = \beta(q)$, Markov inequality yields

$$ \mathbb{P}(\Omega_1^c) \le C \frac{k M^2}{\kappa_0^2 p_{\min}^2} \beta(q). $$

Choosing $x = c_1(n/q)\kappa_0^2 p_{\min}^2/M^2$ in Lemma 11, for $c_1$ small enough yields, for $(n/q)$ large enough,

$$ \|\hat{\mathbf{m}}(\mathbf{c}) - \mathbf{c}^*\|^2 \le \frac{3}{4} R_0^2 + \frac{R_0^2}{8} + \frac{R_0^2}{8} = R_0^2, $$

with probability larger than $1 - 18e^{-c_1 n \kappa_0^2 p_{\min}^2 / q M^2} - C \frac{k M^2}{\kappa_0^2 p_{\min}^2} \beta(q)$, provided $\mathbf{c} \in \mathcal{B}(\mathbf{c}^*, R_0)$. Denoting by $\Omega_2$ the probability event onto which the above equation holds, a straightforward recursion entails that, if $\mathbf{c}^{(0)} \in \mathcal{B}(\mathbf{c}^*, R_0)$, then, for all $t \ge 1$ $\mathbf{c}^{(t)} = \hat{\mathbf{m}}(\mathbf{c}^{(t-1)}) \in \mathcal{B}(\mathbf{c}^*, R_0)$, on $\Omega_2$.

Then, using Lemma 11 iteratively yields that, on $\Omega_2 \cap \Omega_x$, where $\mathbb{P}(\Omega_x^c) \le 2e^{-x}$, for all $t \ge 1$, provided $\mathbf{c}^{(0)} \in \mathcal{B}(\mathbf{c}^*, R_0)$,

$$ \|\mathbf{c}^{(t)} - \mathbf{c}^*\|^2 \le \left(\frac{3}{4}\right)^t \|\mathbf{c}^{(0)} - \mathbf{c}^*\|^2 + C_1 \frac{D_{n/q}^2}{p_{\min}^2} + C_2 \frac{k R^2 M^2}{p_{\min}^2} \left(\frac{1}{n} \sum_{i=1}^n 1_{X_i \neq \tilde{X}_i}\right)^2. \quad (9) $$

Theorem 5 now easily follows. For the first inequality, let $t \ge 1$, then, using Markov inequality again gives

$$ \mathbb{P} \left( \frac{1}{n} \sum_{i=1}^{n} 1_{X_i \neq \tilde{X}_i} \ge \sqrt{q/n} \right) \le \sqrt{\frac{n}{q}} \beta(q). $$

Thus, the assumption $\beta^2(q)/q^3 \le n^{-3}$ entails that

$$ \|\mathbf{c}^{(t)} - \mathbf{c}^*\|^2 \le \left(\frac{3}{4}\right)^t R_0^2 + C_1 \frac{D_{n/q}^2}{p_{\min}^2} + C_2 \frac{k R^2 M^2}{p_{\min}^2(n/q)}, $$

with probability larger than $1 - 18e^{-c_1 n \kappa_0^2 p_{\min}^2 / q M^2} - C \frac{k M^2}{\kappa_0^2 p_{\min}^2} \beta(q) - q/n - 2e^{-x}$ that is larger than $1 - C \frac{q k M^2}{n \kappa_0^2 p_{\min}^2} - 2e^{-x}$.
Since each of the $\tilde{\bar{X}}_{n,j}$'s are i.i.d. sums of discrete measures (the $\tilde{\bar{Y}}_{2s-j}$'s), (Chazal et al., 2021, Lemma 22) readily applies (with sample size $n/(2q)$), giving the result. ■

We now proceed with the first term in (9) as in (Chazal et al., 2021, Proof of Lemma 17). Using the first two inequalities of Lemma 12 with $x = c_1np_{\min}/M$ yields a probability event $\Omega_1$ onto which

$$ \begin{aligned} \tilde{p}_j(\mathbf{c}) &\ge \frac{63}{64}p_j(\mathbf{c}) - \frac{p_{\min}}{64} \ge \frac{31}{32}p_{\min}, \\ \tilde{p}_j(\mathbf{c}) &\le \frac{33}{32}p_j(\mathbf{c}^*). \end{aligned} $$

Combining this with the inequality of Lemma 12 yields, for $n$ large enough and all $\mathbf{c} \in \mathcal{B}(\mathbf{c}^*, R_0)$, with probability larger than $1 - 16e^{-c_1np_{\min}/n} - 2e^{-x}$,

$$ \|\tilde{m}(\mathbf{c}) - \mathbf{c}^*\|^2 \le 0.65 \|\mathbf{c} - \mathbf{c}^*\|^2 + \frac{C}{p_{\min}^2} D_{n/q}^2. \quad (10) $$

The precise derivation of (10) may be found in (Chazal et al., 2021, Proof of Lemma 17, pp.34-35). Plugging (10) into (9) leads to, for a small enough $K$,

$$ \|\hat{m}(\mathbf{c}) - \mathbf{c}^*\|^2 \le \frac{3}{4}\|\mathbf{c} - \mathbf{c}^*\|^2 + \frac{C}{p_{\min}^2} D_{n/q}^2 + C_2\|\hat{m}(\mathbf{c}) - \tilde{m}(\mathbf{c})\|^2, $$

with probability larger than $1 - 16e^{-c_1np_{\min}/n} - 2e^{-x}$.

It remains to control the last term $\|\hat{m}(\mathbf{c}) - \tilde{m}(\mathbf{c})\|^2$. To do so, note that, for every $j = 1, \dots, j,$

$$ \begin{aligned} |\hat{p}_j(\mathbf{c}) - \tilde{p}_j(\mathbf{c})| &= \frac{1}{n} \left| \sum_{i=1}^n X_i(W_j(\mathbf{c})) - \tilde{X}_i(W_j(\mathbf{c})) \right| \\ &\le \frac{M}{n} \sum_{i=1}^n 1_{X_i \ne \tilde{X}_i}, \end{aligned} \quad (11) $$

and

$$ \| (\bar{X}_n(du) - \tilde{\bar{X}}_n(du)) [u1_{W_j(\mathbf{c})}(u)] \| \le \frac{2RM}{n} \sum_{i=1}^n 1_{X_i \ne \bar{X}_i}. $$
For the second inequality, denote by $Z_t$ the random variable

$$Z_t = \left( \|\mathbf{c}^{(t)} - \mathbf{c}^*\|^2 - \left(\frac{3}{4}\right)^t \|\mathbf{c}^{(0)} - \mathbf{c}^*\|^2 - C_1 \frac{qR^2M^2k^2d\log(k)}{np_{\min}^2} - C_2 \frac{kR^2M^2}{p_{\min}^2} \left(\frac{1}{n}\sum_{i=1}^n \mathbb{1}_{X_i \neq \tilde{X}_i}\right)^2 \right)_+ \mathbb{1}_{\Omega_2},$$

and remark that (9) entails

$$\mathbb{P}\left(Z_t \ge C \frac{R^2 M^2 q}{n} x\right) \le \mathbb{P}(\Omega_x^c) \le 2e^{-x}.$$

We deduce that

$$\mathbb{E}(Z_t) \le C \frac{qR^2M^2}{n},$$

which leads to

$$\begin{aligned}
\mathbb{E}(\|\mathbf{c}^{(t)} - \mathbf{c}^*\|^2) &\le \mathbb{E}(\|\mathbf{c}^{(t)} - \mathbf{c}^*\|^2 \mathbb{1}_{\Omega_2}) + 4kR^2MP(\Omega_2^c) \\
&\le \mathbb{E}(Z_t) + \left(\frac{3}{4}\right)^t \|\mathbf{c}^{(0)} - \mathbf{c}^*\|^2 + C_1 \frac{qR^2M^2k^2d\log(k)}{np_{\min}^2} \\
&\quad + C_2 \frac{kR^2M^2}{p_{\min}^2} \mathbb{E}\left(\left(\frac{1}{n}\sum_{i=1}^n \mathbb{1}_{X_i \neq \tilde{X}_i}\right)^2\right) + 4kR^2MP(\Omega_2^c).
\end{aligned}$$

Noting that

$$\mathbb{E}\left(\left(\frac{1}{n}\sum_{i=1}^n \mathbb{1}_{X_i \neq \tilde{X}_i}\right)^2\right) \le \mathbb{E}\left(\frac{1}{n}\sum_{i=1}^n \mathbb{1}_{X_i \neq \tilde{X}_i}\right) = \beta(q),$$

and using

$$\begin{aligned}
\mathbb{P}(\Omega_2^c) &\le \left(e^{-c_1 n \kappa_0^2 p_{\min}^2 / qM^2} + \frac{kM^2}{\kappa_0^2 p_{\min}^2} \beta(q)\right) \\
&\le C \frac{kM^2}{\kappa_0^2 p_{\min}^2} (\beta(q) + (q/n)) \\
&\le C \frac{qkM^2}{n\kappa_0^2 p_{\min}^2}
\end{aligned}$$

whenever $\beta(q) \le q/n$ leads to the result.

<figure><img src="image_18.png" /></figure>

### 7.2.2 PROOF OF THEOREM 6

**Proof** [Proof of Theorem 6] This proof follows the steps of (Chazal et al., 2021, Proof of Lemma 18).

As in the proof of Lemma 11, let $\tilde{X}_1, \dots, \tilde{X}_n$ be such that, denoting by $Y_k$ (resp. $\tilde{Y}_k$) the vector $(X_{(k-1)q+1}, \dots, X_{kq})$ (resp. $(\tilde{X}_{(k-1)q+1}, \dots, \tilde{X}_{kq})$), for $1 \le k \le n/q$, it holds:
On $\Omega_1$, it holds, for every $j = 1, \dots, k$,

$$
\begin{align*}
\| \hat{m}_j(\mathbf{c}) - \tilde{m}_j(\mathbf{c}) \| &= \left\| \frac{\bar{X}_n(du) [u \mathbf{1}_{W_j(\mathbf{c})}(u)]}{\hat{p}_j(\mathbf{c})} - \frac{\tilde{\bar{X}}_n(du) [u \mathbf{1}_{W_j(\mathbf{c})}(u)]}{\tilde{p}_j(\mathbf{c})} \right\| \\
&\le \left\| \bar{X}_n(du) [u \mathbf{1}_{W_j(\mathbf{c})}(u)] \right\| \left| \frac{1}{\hat{p}_j(\mathbf{c})} - \frac{1}{\tilde{p}_j(\mathbf{c})} \right| \\
&\quad + \frac{1}{\tilde{p}_j(\mathbf{c})} \left\| (\bar{X}_n(du) - \tilde{\bar{X}}_n(du)) [u \mathbf{1}_{W_j(\mathbf{c})}(u)] \right\| \\
&\le R \frac{|\hat{p}_j(\mathbf{c}) - \tilde{p}_j(\mathbf{c})|}{\tilde{p}_j(\mathbf{c})} + \frac{2RM}{n\tilde{p}_j(\mathbf{c})} \sum_{i=1}^n \mathbf{1}_{X_i \ne \tilde{X}_i} \\
&\le C \frac{RM}{np_{\min}} \sum_{i=1}^n \mathbf{1}_{X_i \ne \tilde{X}_i}.
\end{align*}
$$

Squaring and taking the sum with respect to $j$ gives the result.

<figure><img src="image_18.png" /></figure>

### 7.2.4 PROOF OF PROPOSITION 7

**Proof** [Proof of Proposition 7] Let $Z_1, \dots, Z_n$ denote the sequence $\|\tilde{v}_1\|, \dots, \|\tilde{v}_n\|$, that is a stationary $\beta$-mixing sequence of real-valued random variables. For $s \in \mathbb{R}$, we let

$$F_n(t) = \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}_{Z_i > t},$$

and $F(t) = \mathbb{P}(Z > t)$, and $\hat{t}$ be such that $F_n(\hat{t}) \le \alpha - \delta$. In the i.i.d. case, we might bound $\sup_t(F(t) - F_n(t))/\sqrt{F_n(t)}$ using a standard inequality such as in (Boucheron et al., 2005, Section 5.1.2).

As for the proofs of Theorem 5 and 6, we compare with the i.i.d. case by introducing auxiliary variables.

We let $\tilde{Z}_1, \dots, \tilde{Z}_n$ be such that, denoting by $Y_k$ (resp. $\tilde{Y}_k$) the vector $(Z_{(k-1)q+1}, \dots, Z_{kq})$ (resp. $(\tilde{Z}_{(k-1)q+1}, \dots, \tilde{Z}_{kq})$), it holds

* For every $1 \le k \le n/q$, $Y_k \sim \tilde{Y}_k$, and $\mathbb{P}(Y_k \ne \tilde{Y}_k) \le \beta(q)$.

* $(Y_{2k})_{k \ge 1}$ are independent, as well as $(Y_{2k-1})_{k \ge 1}$.

Let $\tilde{F}_n(t)$ denote $\sum_{i=1}^n \mathbf{1}_{\tilde{Z}_i > t}$. Then, for any $t \in \mathbb{R}$, we have

$$\tilde{F}_n(t) \le F_n(t) + \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}_{Z_i \ne \tilde{Z}_i}.$$
• For every $k \ge 1$ $Y_k$ has the same distribution as $\tilde{Y}_k$, and $\mathbb{P}(\tilde{Y}_k \ne Y_k) \le \beta(q)$.

• The random variables $(Y_{2k})_{k \ge 1}$ are independent, as well as the variables $(Y_{2k-1})_{k \ge 1}$.

Let $A_{\perp}$ denote the event

$$A_{\perp} = \{ \forall j = 1, \dots, n/q \quad Y_j = \tilde{Y}_j \}.$$

A standard union bound yields that $\mathbb{P}(A_{\perp}^c) \le \frac{n}{q}\beta(q)$. On $A_{\perp}$, the minibatches used by Algorithm 4 may be considered as independent, so that the main lines of (Chazal et al., 2021, Proof of Lemma 18) readily applies, replacing $X_i$'s by $\tilde{X}_i$'s. In what follows we let $\tilde{\mathbf{c}}^{(t)}$ denote the output of the t-th iteration of Algorithm 4 based on $\tilde{X}_1, \dots, \tilde{X}_n$.

Assume that $n \ge k$, and $q \ge C \frac{M^2}{p_{\min}^2} \log(n)$, for a large enough constant $C$ that only depends on $\int_0^1 \beta^{-1}(u)du$, to be fixed later. For $t \le n/(4q) = T$, let $A_{t,1}$ and $A_{t,3}$ denote the events

$$A_{t,1} = \{ \forall j = 1, \dots, k \quad |\tilde{p}_j(t) - p_j(t)| \le \frac{p_{\min}}{128} \},$$

$$A_{t,3} = \left\{ \forall j = 1, \dots, k \quad \left\| \int (\tilde{c}_j^{(t)} - u) \mathbb{1}_{W_j(\tilde{\mathbf{c}}^{(t)})} (u) (\tilde{X}_{B_t^{(3)}} - \mathbb{E}(X))(du) \right\| \le 8R \sqrt{\frac{M k d p_{\min}}{C}} \right\},$$

where $\tilde{p}_j(t) = \tilde{X}_{B_t^{(1)}}(W_j(\tilde{\mathbf{c}}^{(t)}))$. Then, according to Theorem 9 with $x = 2 \log(n)$ and Lemma 10 to bound the corresponding $\sigma$, for $j \in \{1, 3\}$, $\mathbb{P}(A_{t,j}) \le 4dk/n^2 + 2kd\beta(q_n/18)$, for $n$ large enough.

Further, define

$$A_{\le t} = \bigcap_{j \le t} A_{j,1} \cap A_{j,3}.$$

Then, provided that $q \ge c_0 \frac{k^2 d M^2}{p_{\min}^2 \kappa_0^2} \log(n)$, where $c_0$ only depends on $\int_0^1 \beta^{-1}(u)du$, we may prove recursively that

$$\forall p \le t \quad \tilde{\mathbf{c}}^{(p)} \in \mathcal{B}(\mathbf{c}^*, R_0)$$

on $A_{\le t}$ whenever $\tilde{\mathbf{c}}^{(0)} = \mathbf{c}^{(0)} \in \mathcal{B}(\mathbf{c}^*, R_0)$ (first step of the proof of (Chazal et al., 2021, Lemma 18)).

Next, denoting by $a_t = \|\tilde{\mathbf{c}}^{(t)} - \mathbf{c}^*\|^2 \mathbb{1}_{A_{\le t}}$, we may write

$$\mathbb{E}(a_{t+1}) \le \mathbb{E}(\|\tilde{\mathbf{c}}^{(t+1)} - \mathbf{c}^*\|^2 \mathbb{1}_{A_{t+1,1}} \mathbb{1}_{A_{\le t}}) + R_1,$$

with

$$R_1 \le 4kR^2 (\mathbb{P}(A_{t+1,3}^c))$$

$$\le 16k^2 d R^2 (n^{-2} + \beta(q/18))$$

$$\le 32k^2 d R^2 (q/n)^2,$$
If $\Omega_1$ is the event $\{\frac{1}{n}\sum_{i=1}^n 1_{Z_i \neq \tilde{Z}_i} \le \sqrt{\frac{\alpha q}{n}}\}$, that has probability larger than $1-\beta(q)\sqrt{n/(\alpha q)}$ (using Markov inequality as before), then on $\Omega_1$ it readily holds

$$ \tilde{F}_n(\hat{t}) \le F_n(\hat{t}) + \sqrt{\frac{\alpha q}{n}} \\ \le \alpha - \delta + \sqrt{\frac{\alpha q}{n}}, $$

so that we may write, on the same event,

$$ F(\hat{t}) = F(\hat{t}) - \tilde{F}_n(\hat{t}) + \tilde{F}_n(\hat{t}) \\ \le \alpha - \delta + \sqrt{\frac{\alpha q}{n}} + (F(\hat{t}) - \tilde{F}_n(\hat{t})). \quad (12) $$

It remains to control the stochastic term $(F(\hat{t}) - \tilde{F}_n(\hat{t}))$. To do so, we denote by

$$ \tilde{X}_{j,0}(t) = \frac{1}{q} \sum_{i=2(j-1)q+1}^{(2j-1)q} 1_{\tilde{Z}_i > t}, \\ \tilde{X}_{j,1}(t) = \frac{1}{q} \sum_{i=(2j-1)q+1}^{2jq} 1_{\tilde{Z}_i > t}, $$

for $j \in [1, n/(2q)]$ and $t \in \mathbb{R}$. Note that, for any $\sigma \in \{0, 1\}$, $\tilde{X}_{j,\sigma}$'s are i.i.d., take values in $[0, 1]$, and have expectation $F(t)$. Next, we define, for $1 \le j \le n/2q$ and $t \in \mathbb{R}$,

$$ \tilde{F}_{n,0}(t) = \frac{2q}{n} \sum_{j=1}^{n/2q} \tilde{X}_{j,0}(t) \\ \tilde{F}_{n,1}(t) = \frac{2q}{n} \sum_{j=1}^{n/2q} \tilde{X}_{j,1}(t), $$

and we note that $\tilde{F}_n(t) = \frac{1}{2}(\tilde{F}_{n,0}(t) + \tilde{F}_{n,1}(t))$. Since the $\tilde{F}_{n,\sigma}$'s are sums of i.i.d. random variables, the following concentration bound follows.

**Lemma 13** For $j \in \{0, 1\}$, and $x$ such that $(n/2q)x^2 \ge 1$, it holds

$$ \mathbb{P} \left( \sup_{t \in \mathbb{R}} \frac{(F(t) - \tilde{F}_{n,j}(t))}{\sqrt{F(t)}} \ge 2x \right) \le 2ne^{-(n/2q)x^2}. $$

A proof of Lemma 13 is postponed to the following Section 7.2.5. Now, choosing $x = 2\sqrt{\frac{q \log(n)}{n}}$ entails that, with probability larger than $1 - 4(q/n) - \beta(q)\sqrt{n/(\alpha q)}$,

$$ F(\hat{t}) \le \alpha - \delta + \sqrt{\frac{\alpha q}{n}} + 4\sqrt{\frac{q \log(n)}{n}} \sqrt{F(\hat{t})}, $$
recalling that $\beta(q/18)/q^2 \le n^{-2}$. Proceeding as in (Chazal et al., 2021, Proof of Lemma 18),
we may further bound

$$
\mathbb{E}(\|\tilde{\mathbf{c}}^{(t+1)} - \mathbf{c}^*\|^2 \mathbf{1}_{A_{t+1,1}} \mathbf{1}_{A_{\le t}}) \le \left(1 - \frac{2 - K_1}{t+1}\right) \mathbb{E}(a_t) + \frac{12k d M R^2}{p_{\min}(t+1)^2},
$$

for some $K_1 \le 0.5$. Noticing that $k \le M/p_{\min}$ and $t+1 \le T = n/(4q)$ yields that

$$
\mathbb{E}(a_{t+1}) \le \left(1 - \frac{2 - K_1}{t + 1}\right) \mathbb{E}(a_t) + \frac{14k d M R^2}{p_{\min}(t + 1)^2}.
$$

Following (Chazal et al., 2021, Proof of Theorem 10), a standard recursion entails

$$
\mathbb{E}(a_t) \le \frac{28k d M R^2}{p_{\min} t},
$$

for $t \le n/(4q)$. At last, since $\|\tilde{\mathbf{c}}^{(T)} - \mathbf{c}^*\|^2 \mathbf{1}_{A_\perp} = \|\mathbf{c}^{(T)} - \mathbf{c}^*\|^2 \mathbf{1}_{A_\perp}$, we conclude that

$$
\begin{align*}
\mathbb{E}\|\mathbf{c}^{(T)} - \mathbf{c}^*\|^2 &\le \mathbb{E}(\|\tilde{\mathbf{c}}^{(T)} - \mathbf{c}^*\|^2) + 4kR^2\mathbb{P}(A_{\perp}^c) \\
&\le \mathbb{E}(\|\tilde{\mathbf{c}}^{(T)} - \mathbf{c}^*\|^2 \mathbf{1}_{A_{\le T}}) + 4kR^2\mathbb{P}(A_{\le T}^c) + \frac{4kR^2}{(n/q)} \\
&\le \mathbb{E}(a_T) + \frac{16k^2R^2d}{(n/q)} \\
&\le 128\frac{kMR^2d}{p_{\min}(n/q)},
\end{align*}
$$

where $k \le M/p_{\min}$ and $T = \frac{(n/q)}{4}$ have been used.

<figure><img src="image_19.png" /></figure>

7.2.3 PROOF OF LEMMA 11

**Proof** [Proof of Lemma 11] Assume that $\mathbf{c} \in \mathcal{B}(\mathbf{c}^*, R_0)$, for some optimal $\mathbf{c}^* \in \mathcal{C}_{opt}$. Then, for any $K > 0$, it holds

$$
\|\hat{m}(\mathbf{c}) - \mathbf{c}^*\|^2 \le (1+K)\|\hat{m}(\mathbf{c}) - \mathbf{c}^*\|^2 + (1+K^{-1})\|\hat{m}(\mathbf{c}) - \hat{m}(\mathbf{c})\|^2. \quad (10)
$$

The first term of the right hand side may be controlled using a slight adaptation of
(Chazal et al., 2021, Lemma 22).

**Lemma 12** With probability larger than $1 - 16e^{-x}$, for all $\mathbf{c} \in \mathcal{B}(0, R)^k$ and $j \in [1, k]$, it holds

$$
\begin{align*}
\tilde{p}_j(\mathbf{c}) &\ge p_j(\mathbf{c}) - \sqrt{p_j(\mathbf{c})} \sqrt{\frac{8Mc_0q \log(k) \log(2nN_{\max})}{n}} + \frac{8Mqx}{n}, \\
\tilde{p}_j(\mathbf{c}) &\le p_j(\mathbf{c}) + \frac{8Mc_0q \log(k) \log(2nN_{\max})}{n} + \frac{8Mqx}{n} \\
&\quad + \sqrt{\frac{8Mc_0q \log(k) \log(2nN_{\max})}{n}} + \frac{8Mqx}{n} \sqrt{p_j(\mathbf{c})},
\end{align*}
$$
which leads to

$$ \sqrt{F(\hat{t})} \le 2\sqrt{\frac{q \log(n)}{n}} + \sqrt{\alpha - \delta + \sqrt{\frac{\alpha q}{n}} + 4\frac{q \log(n)}{n}} $$

Choosing $\delta \ge 4\sqrt{\alpha}\sqrt{\frac{q \log(n)}{n}} + \sqrt{\frac{\alpha q}{n}}$ ensures that the right-hand side is smaller than $\sqrt{\alpha}$. ■

### 7.2.5 PROOF OF LEMMA 13

**Proof** [Proof of Lemma 13] The proof follows the one of (Chazal et al., 2021, Lemma 22) verbatim, at the exception of the capacity bound, that we discuss now. To lighten notation we assume that we have a $n/(2q)$ sample of $Y_i$'s, with $Y_i = (Z_{(i-1)q+1}, \dots, Z_{iq}) \in \mathbb{R}^q$, and we consider the set of functionals

$$ \mathcal{F} = \left\{ y = (z_1, \dots, z_q) \mapsto \frac{1}{q} \sum_{i=1}^{q} 1_{z_i > t} \right\} $$

Following (Chazal et al., 2021, Lemma 22), if $S_{\mathcal{F}}(y_1, \dots, y_{n/(2q)})$ denotes the cardinality of $\{f(y_1), \dots, f(y_{n/(2q)}) | f \in \mathcal{F}\}$, we have to bound

$$ S_{\mathcal{F}}(Y_1, \dots, Y_{n/(2q)}, Y'_1, \dots, Y'_{n/(2q)}) $$

where the $Y'_i$'s are i.i.d. copies of the $Y_i$'s. Since, for every $y_1, \dots, y_{n/q}$, recalling that $y_i = (z_{(i-1)q+1}, \dots, z_{iq})$, it holds

$$ S_{\mathcal{F}}(y_1, \dots, y_{n/q}) \le \{(1_{z_1 > t}, \dots, 1_{z_n > t}) | t \in \mathbb{R}\}, $$

we deduce that

$$ S_{\mathcal{F}}(Y_1, \dots, Y_{n/(2q)}, Y'_1, \dots, Y'_{n/(2q)}) \le n. $$

The remaining of the proof follows verbatim (Chazal et al., 2021, Lemma 22). ■

## References

H. Adams, T. Emerson, M. Kirby, R. Neville, C. Peterson, P. Shipman, S. Chepushtanova, E. Hanson, F. Motta, and L. Ziegelmeier. Persistence images: a stable vector representation of persistent homology. *J. Mach. Learn. Res.*, 18:Paper No. 8, 35, 2017. ISSN 1532-4435.

A. Agarwal and J. C. Duchi. The generalization ability of online algorithms for dependent data. *IEEE Trans. Inform. Theory*, 59(1):573–587, 2013. ISSN 0018-9448,1557-9654. doi: 10.1109/TIT.2012.2212414. URL https://doi.org/10.1109/TIT.2012.2212414.

S. Arlot, A. Celisse, and Z. Harchaoui. A kernel multiple change-point algorithm via model selection. *J. Mach. Learn. Res.*, 20:Paper No. 162, 56, 2019. ISSN 1532-4435,1533-7928.
where $c_0$ is an absolute constant. Moreover, with probability larger than $1 - 2e^{-x}$, it holds

$$ \sup_{\mathbf{c} \in \mathcal{B}(0, R)^k} \left\| \left( \int (c_j - u) \mathbb{1}_{W_j(\mathbf{c})} (u) (\tilde{\bar{X}}_n - \mathbb{E}(X))(du) \right)_{j=1, \dots, k} \right\| \le C_0 \frac{RM\sqrt{q}}{\sqrt{n}} \left( k\sqrt{d\log(k)} + \sqrt{x} \right), $$

where $C_0$ is an absolute constant.

**Proof** [Proof of Lemma 12] We intend here to recover the standard i.i.d. bounds given in (Chazal et al., 2021, Lemma 22). To this aim, we let $\tilde{p}_{j,0}(\mathbf{c})$ and $\tilde{p}_{j,1}(\mathbf{c})$ be defined by

$$ \tilde{p}_{j,r}(\mathbf{c}) = \frac{2q}{n} \sum_{s=1}^{n/2q} \tilde{Y}_{2s-r}(W_j(\mathbf{c})), $$

for $r \in \{0, 1\}$, where $\tilde{Y}_{2s-r} = \frac{1}{q} \sum_{t=(2s-r-1)q+1}^{(2s-r)q} \tilde{X}_t$ is a measure in $\mathcal{M}(R, M)$, with total number of support points bounded by $qN_{\max}$, and remark that

$$ \tilde{p}_j(\mathbf{c}) = \frac{1}{2} (\tilde{p}_{j,0}(\mathbf{c}) + \tilde{p}_{j,1}(\mathbf{c})). $$

Since $\mathbb{E}(\tilde{Y}_{2s-r})(W_j(\mathbf{c})) = p_j(\mathbf{c})$, and the $\tilde{p}_{j,r}(\mathbf{c})$'s are sums of $n/2q$ independent measures evaluated on $W_j(\mathbf{c})$, we may readily apply (Chazal et al., 2021, Lemma 22) replacing $n$ by $n/(2q)$ to each of them, leading to the deviation bounds on the $\tilde{p}_j(\mathbf{c})$'s.

For the third inequality of Lemma 12, denoting by

$$ \tilde{X}_{n,j} = \frac{2q}{n} \sum_{s=1}^{n/2q} \tilde{Y}_{2s-j}, $$

for $j \in \{0, 1\}$, it holds, for any $\mathbf{c} \in \mathcal{B}(0, R)^k$,

$$ \left\| \left( \int (c_j - u) \mathbb{1}_{W_j(\mathbf{c})} (u) (\tilde{\bar{X}}_n - \mathbb{E}(X))(du) \right)_{j=1, \dots, k} \right\| \le \frac{1}{2} \left( \left\| \left( \int (c_j - u) \mathbb{1}_{W_j(\mathbf{c})} (u) (\tilde{\bar{X}}_{n,0} - \mathbb{E}(X))(du) \right)_{j=1, \dots, k} \right\| + \left\| \left( \int (c_j - u) \mathbb{1}_{W_j(\mathbf{c})} (u) (\tilde{\bar{X}}_{n,1} - \mathbb{E}(X))(du) \right)_{j=1, \dots, k} \right\| \right). $$

Since each of the $\tilde{X}_{n,j}$'s are i.i.d. sums of discrete measures (the $\tilde{Y}_{2s-j}$'s), (Chazal et al., 2021, Lemma 22) readily applies (with sample size $n/(2q)$), giving the result. ■

We now proceed with the first term in (10) as in (Chazal et al., 2021, Proof of Lemma 17). Using the first two inequalities of Lemma 12 with $x = c_1np_{\min}/M$ yields a probability event $\Omega_1$ onto which

$$ \tilde{p}_j(\mathbf{c}) \ge \frac{63}{64} p_j(\mathbf{c}) - \frac{p_{\min}}{64} \ge \frac{31}{32} p_{\min}, $$

$$ \tilde{p}_j(\mathbf{c}) \le \frac{33}{32} p_j(\mathbf{c}^*). $$
TADA

J.-D. Boissonnat, F. Chazal, and M. Yvinec. *Geometric and Topological Inference*, volume 57.
Cambridge University Press, 2018.

S. Boucheron, O. Bousquet, and G. Lugosi. Theory of classification: a survey of some recent advances. *ESAIM Probab. Stat.*, 9:323-375, 2005. ISSN 1292-8100,1262-3318. doi: 10.1051/ps:2005018. URL https://doi.org/10.1051/ps:2005018.

A. E. Y. Bourakna, M. K. Chung, and H. Ombao. Modeling and simulating dependence in networks using topological data analysis, 2022.

C. Brécheteau, A. Fischer, and C. Levrard. Robust Bregman clustering. *The Annals of Statistics*, 49(3):1679–1701, 2021. doi: 10.1214/20-AOS2018. URL https://doi.org/10.1214/20-AOS2018.

L. Breiman. Random forests. 45:5–32, 2001-10. doi: 10.1023/A:1010950718922.

P. Bruillard, K. Nowak, and E. Purvine. Anomaly detection using persistent homology.
In *2016 Cybersecurity Symposium (CYBERSEC)*, pages 7–12, Los Alamitos, CA, USA,
apr 2016. IEEE Computer Society. doi: 10.1109/CYBERSEC.2016.009. URL https://doi.ieeecomputersociety.org/10.1109/CYBERSEC.2016.009.

F. Chazal and V. Divol. The density of expected persistence diagrams and its kernel based estimation. In *34th International Symposium on Computational Geometry*, volume 99 of *LIPIcs. Leibniz Int. Proc. Inform.*, pages Art. No. 26, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018.

F. Chazal and B. Michel. An introduction to topological data analysis: fundamental and practical aspects for data scientists. *Frontiers in artificial intelligence*, 4:108, 2021.

F. Chazal, V. de Silva, and S. Oudot. Persistence stability for geometric complexes.
*Geometriae Dedicata*, 173(1):193–214, 2014.

F. Chazal, V. de Silva, M. Glisse, and S. Oudot. *The structure and stability of persistence modules*. Springer International Publishing, 2016.

F. Chazal, C. Levrard, and M. Royer. Clustering of measures via mean measure quantization.
*Electronic Journal of Statistics*, 15(1):2060–2104, 2021. doi: 10.1214/21-EJS1834. URL https://doi.org/10.1214/21-EJS1834.

S. Chrétien, B. Gao, A. Thebault-Guiochon, and R. Vaucher. Time topological analysis of eeg using signature theory, 2024.

M. Dindin, Y. Umeda, and F. Chazal. Topological data analysis for arrhythmia detection through modular neural networks, 2019.

P. Doukhan. *Mixing*, volume 85 of *Lecture Notes in Statistics*. Springer-Verlag, New York, 1994. ISBN 0-387-94214-9. doi: 10.1007/978-1-4612-2642-0. URL https://doi.org/10.1007/978-1-4612-2642-0. Properties and examples.
Combining this with the inequality of Lemma 12 yields, for $n$ large enough and all $\mathbf{c} \in \mathcal{B}(\mathbf{c}^*, R_0)$, with probability larger than $1 - 16e^{-c_1 np_{\min}/n} - 2e^{-x}$,

$$ \|\tilde{m}(\mathbf{c}) - \mathbf{c}^*\|^2 \le 0.65 \|\mathbf{c} - \mathbf{c}^*\|^2 + \frac{C}{p_{\min}^2} D_{n/q}^2. \quad (11) $$

The precise derivation of (11) may be found in (Chazal et al., 2021, Proof of Lemma 17, pp.34-35). Plugging (11) into (10) leads to, for a small enough $K$,

$$ \|\hat{m}(\mathbf{c}) - \mathbf{c}^*\|^2 \le \frac{3}{4} \|\mathbf{c} - \mathbf{c}^*\|^2 + \frac{C}{p_{\min}^2} D_{n/q}^2 + C_2 \|\hat{m}(\mathbf{c}) - \tilde{m}(\mathbf{c})\|^2, $$

with probability larger than $1 - 16e^{-c_1 np_{\min}/n} - 2e^{-x}$.

It remains to control the last term $\|\hat{m}(\mathbf{c}) - \tilde{m}(\mathbf{c})\|^2$. To do so, note that, for every $j = 1, \dots, j,$

$$ \begin{aligned} |\hat{p}_j(\mathbf{c}) - \tilde{p}_j(\mathbf{c})| &= \frac{1}{n} \left| \sum_{i=1}^n X_i(W_j(\mathbf{c})) - \tilde{X}_i(W_j(\mathbf{c})) \right| \\ &\le \frac{M}{n} \sum_{i=1}^n 1_{X_i \ne \tilde{X}_i}, \end{aligned} \quad (12) $$

and

$$ \|(\bar{X}_n(du) - \tilde{X}_n(du)) [u1_{W_j(\mathbf{c})}(u)]\| \le \frac{2RM}{n} \sum_{i=1}^n 1_{X_i \ne \tilde{X}_i}. $$

On $\Omega_1$, it holds, for every $j = 1, \dots, k$,

$$ \begin{aligned} \|\hat{m}_j(\mathbf{c}) - \tilde{m}_j(\mathbf{c})\| &= \left\| \frac{\bar{X}_n(du) [u1_{W_j(\mathbf{c})}(u)]}{\hat{p}_j(\mathbf{c})} - \frac{\tilde{X}_n(du) [u1_{W_j(\mathbf{c})}(u)]}{\tilde{p}_j(\mathbf{c})} \right\| \\ &\le \left\| \bar{X}_n(du) [u1_{W_j(\mathbf{c})}(u)] \right\| \left| \frac{1}{\hat{p}_j(\mathbf{c})} - \frac{1}{\tilde{p}_j(\mathbf{c})} \right| \\ &\quad + \frac{1}{\tilde{p}_j(\mathbf{c})} \left\| (\bar{X}_n(du) - \tilde{X}_n(du)) [u1_{W_j(\mathbf{c})}(u)] \right\| \\ &\le R \frac{|\hat{p}_j(\mathbf{c}) - \tilde{p}_j(\mathbf{c})|}{\tilde{p}_j(\mathbf{c})} + \frac{2RM}{n\tilde{p}_j(\mathbf{c})} \sum_{i=1}^n 1_{X_i \ne \tilde{X}_i} \\ &\le C \frac{RM}{np_{\min}} \sum_{i=1}^n 1_{X_i \ne \tilde{X}_i}. \end{aligned} $$

Squaring and taking the sum with respect to $j$ gives the result.

<figure><img src="image_20.png" /></figure>
P. Doukhan, P. Massart, and E. Rio. Invariance principles for absolutely regular empirical processes. *Ann. Inst. H. Poincaré Probab. Statist.*, 31(2):393-427, 1995. ISSN 0246-0203.
URL http://www.numdam.org/item?id=AIHPB_1995__31_2_393_0.

H. Edelsbrunner and J. Harer. *Computational topology: an introduction*. American Mathematical Society, 2010.

P. G., E. P., T. F., C.-H. R., N. D., H. P.J., and V. F. Homological scaffolds of brain functional networks. *Journal of the Royal Society Interface*, 11(101), 2014. doi: 10.1098/rsif.2014.0873.

N. Heim and J. E. Avery. Adaptive anomaly detection in chaotic time series with a spatially aware echo state network. *ArXiv*, abs/1909.01709, 2019. URL https://api.semanticscholar.org/CorpusID:202541761.

S. Herbold. Autorank: A python package for automated ranking of classifiers. *Journal of Open Source Software*, 5(48):2173, 2020. doi: 10.21105/joss.02173. URL https://doi.org/10.21105/joss.02173.

T. K. K. Ho, A. Karami, and N. Armanfard. Graph-based time-series anomaly detection: A survey. *arXiv preprint arXiv:2302.00058*, 2023.

M. Hubert, M. Debruyne, and P. J. Rousseeuw. Minimum covariance determinant and extensions. *Wiley Interdiscip. Rev. Comput. Stat.*, 10(3):e1421, 11, 2018. ISSN 1939-5108,1939-0068. doi: 10.1002/wics.1421. URL https://doi.org/10.1002/wics.1421.

V. Jacob, F. Song, A. Stiegler, B. Rad, Y. Diao, and N. Tatbul. Exathlon: a benchmark for explainable anomaly detection over time series. 14(11):2613-2626, 2021-07. ISSN 2150-8097. doi: 10.14778/3476249.3476307. URL https://doi.org/10.14778/3476249.3476307.

S. Jana, J. Fan, and S. Kulkarni. A general theory for robust clustering via trimmed mean, 2024.

C. Levrard. Nonasymptotic bounds for vector quantization in hilbert spaces. *Ann. Statist.*, 43(2):592-619, 04 2015. doi: 10.1214/14-AOS1293. URL https://doi.org/10.1214/14-AOS1293.

C. Levrard. Quantization/clustering: when and why does k-means work. *Journal de la Société Française de Statistiques*, 159(1), 2018.

S. Li, W. Song, C. Zhao, Y. Zhang, W. Shen, J. Hai, J. Lu, and Y. Xie. An anomaly detection method for multiple time series based on similarity measurement and louvain algorithm. *Procedia Computer Science*, 200:1857-1866, 2022.

F. T. Liu, K. M. Ting, and Z.-H. Zhou. Isolation forest. In *2008 Eighth IEEE International Conference on Data Mining*, pages 413-422, 2008. doi: 10.1109/ICDM.2008.17.

D. J. McDonald, C. R. Shalizi, and M. Schervish. Estimating beta-mixing coefficients via histograms. *Electron. J. Stat.*, 9(2):2855-2883, 2015. ISSN 1935-7524. doi: 10.1214/15-EJS1094. URL https://doi.org/10.1214/15-EJS1094.
### 7.2.4 PROOF OF PROPOSITION 7

**Proof** [Proof of Proposition 7] Let $Z_1, \dots, Z_n$ denote the sequence $\|\tilde{v}_1\|, \dots, \|\tilde{v}_n\|$, that is a stationary $\beta$-mixing sequence of real-valued random variables. For $t \in \mathbb{R}$, we let

$$F_n(t) = \frac{1}{n} \sum_{i=1}^{n} 1_{Z_i > t},$$

$F(t) = \mathbb{P}(Z > t)$, and $\hat{t}$ be such that $F_n(\hat{t}) \le \alpha - \delta$. In the i.i.d. case, we might bound $\sup_t(F(t) - F_n(t))/\sqrt{F_n(t)}$ using a standard inequality such as in (Boucheron et al., 2005, Section 5.1.2).

As for the proofs of Theorem 5 and 6, we compare with the i.i.d. case by introducing auxiliary variables.

We let $\tilde{Z}_1, \dots, \tilde{Z}_n$ be such that, denoting by $Y_k$ (resp. $\tilde{Y}_k$) the vector $(Z_{(k-1)q+1}, \dots, Z_{kq})$ (resp. $(\tilde{Z}_{(k-1)q+1}, \dots, \tilde{Z}_{kq}))$, it holds

* For every $1 \le k \le n/q$, $Y_k \sim \tilde{Y}_k$, and $\mathbb{P}(Y_k \ne \tilde{Y}_k) \le \beta(q)$.

* $(Y_{2k})_{k \ge 1}$ are independent, as well as $(Y_{2k-1})_{k \ge 1}$.

Let $\tilde{F}_n(t)$ denote $\sum_{i=1}^n 1_{\tilde{Z}_i > t}$. Then, for any $t \in \mathbb{R}$, we have

$$\tilde{F}_n(t) \le F_n(t) + \frac{1}{n} \sum_{i=1}^{n} 1_{Z_i \ne \tilde{Z}_i}.$$

If $\Omega_1$ is the event $\{\frac{1}{n} \sum_{i=1}^n 1_{Z_i \ne \tilde{Z}_i} \le \sqrt{\frac{\alpha q}{n}}\}$, that has probability larger than $1 - \beta(q)\sqrt{n/(\alpha q)}$ (using Markov inequality as before), then on $\Omega_1$ it readily holds

$$\tilde{F}_n(\hat{t}) \le F_n(\hat{t}) + \sqrt{\frac{\alpha q}{n}} \\ \le \alpha - \delta + \sqrt{\frac{\alpha q}{n}},$$

so that we may write, on the same event,

$$F(\hat{t}) = F(\hat{t}) - \tilde{F}_n(\hat{t}) + \tilde{F}_n(\hat{t}) \\ \le \alpha - \delta + \sqrt{\frac{\alpha q}{n}} + (F(\hat{t}) - \tilde{F}_n(\hat{t})). \quad (13)$$

It remains to control the stochastic term $(F(\hat{t}) - \tilde{F}_n(\hat{t}))$. To do so, we denote by

$$\tilde{X}_{j,0}(t) = \frac{1}{q} \sum_{i=2(j-1)q+1}^{(2j-1)q} 1_{\tilde{Z}_i > t},$$

$$\tilde{X}_{j,1}(t) = \frac{1}{q} \sum_{i=(2j-1)q+1}^{2jq} 1_{\tilde{Z}_i > t},$$
A. H. Mohammed, M. Cabrerizo, A. Pinzon, I. Yaylali, P. Jayakar, and M. Adjouadi. Graph neural networks in eeg spike detection. *Artificial Intelligence in Medicine*, 145: 102663, 2023. ISSN 0933-3657. doi: https://doi.org/10.1016/j.artmed.2023.102663. URL https://www.sciencedirect.com/science/article/pii/S093336572300177X.

M. Mohri and A. Rostamizadeh. Stability bounds for stationary φ-mixing and β-mixing processes. *J. Mach. Learn. Res.*, 11:789–814, 2010. ISSN 1532-4435,1533-7928.

H. Ombao and M. Pinto. Spectral dependence, 2021.

J. Paparrizos, P. Boniol, T. Palpanas, R. S. Tsay, A. Elmore, and M. J. Franklin. Volume under the surface: a new accuracy evaluation measure for time-series anomaly detection. *Proc. VLDB Endow.*, 15(11):2774–2787, jul 2022a. ISSN 2150-8097. doi: 10.14778/3551793.3551830. URL https://doi.org/10.14778/3551793.3551830.

J. Paparrizos, Y. Kang, P. Boniol, R. S. Tsay, T. Palpanas, and M. J. Franklin. Tsb-uad: an end-to-end benchmark suite for univariate time-series anomaly detection. *Proc. VLDB Endow.*, 15(8):1697–1711, apr 2022b. ISSN 2150-8097. doi: 10.14778/3529337.3529354. URL https://doi.org/10.14778/3529337.3529354.

F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. *Journal of Machine Learning Research*, 12:2825–2830, 2011.

T. D. Pham and L. T. Tran. Some mixing properties of time series models. *Stochastic Process. Appl.*, 19(2):297–303, 1985. ISSN 0304-4149,1879-209X. doi: 10.1016/0304-4149(85) 90031-6. URL https://doi.org/10.1016/0304-4149(85)90031-6.

Y. V. Prokhorov. Convergence of random processes and limit theorems in probability theory. *Teor. Veroyatnost. i Primenen.*, 1:177–238, 1956. ISSN 0040-361X.

N. Ravishanker and R. Chen. Topological data analysis (tda) for time series, 2019.

I. W. Renner, J. Elith, A. Baddeley, W. Fithian, T. Hastie, S. J. Phillips, G. Popovic, and D. I. Warton. Point process models for presence-only analysis. *Methods in Ecology and Evolution*, 6(4):366–379, 2015. doi: 10.1111/2041-210X.12352. URL https://besjournals.onlinelibrary.wiley.com/doi/abs/10.1111/2041-210X.12352.

E. Rio. Covariance inequalities for strongly mixing processes. *Ann. Inst. H. Poincaré Probab. Statist.*, 29(4):587–597, 1993. ISSN 0246-0203. URL http://www.numdam.org/item?id=AIHPB_1993__29_4_587_0.

P. J. Rousseeuw and K. V. Driessen. A fast algorithm for the minimum covariance determinant estimator. *Technometrics*, 41(3):212–223, 1999. doi: 10.1080/00401706.1999.10485670. URL https://www.tandfonline.com/doi/abs/10.1080/00401706.1999.10485670.

M. Royer, F. Chazal, C. Levrard, Y. Umeda, and Y. Ike. Atol: Measure vectorization for automatic topologically-oriented learning. In A. Banerjee and K. Fukumizu, editors,
for $j \in [1, n/(2q)]$ and $t \in \mathbb{R}$. Note that, for any $\sigma \in \{0, 1\}$, $\tilde{X}_{j,\sigma}$'s are i.i.d., take values in $[0, 1]$, and have expectation $F(t)$. Next, we define, for $1 \le j \le n/2q$ and $t \in \mathbb{R}$,

$$ \tilde{F}_{n,0}(t) = \frac{2q}{n} \sum_{j=1}^{n/2q} \tilde{X}_{j,0}(t), $$

$$ \tilde{F}_{n,1}(t) = \frac{2q}{n} \sum_{j=1}^{n/2q} \tilde{X}_{j,1}(t), $$

and we note that $\tilde{F}_n(t) = \frac{1}{2}(\tilde{F}_{n,0}(t) + \tilde{F}_{n,1}(t))$. Since the $\tilde{F}_{n,\sigma}$'s are sums of i.i.d. random variables, the following concentration bound follows.

**Lemma 13** For $j \in \{0, 1\}$, and $x$ such that $(n/2q)x^2 \ge 1$, it holds

$$ \mathbb{P} \left( \sup_{t \in \mathbb{R}} \frac{(F(t) - \tilde{F}_{n,j}(t))}{\sqrt{F(t)}} \ge 2x \right) \le 2ne^{-(n/2q)x^2}. $$

A proof of Lemma 13 is postponed to the following Section 7.2.5. Now, choosing $x = 2\sqrt{\frac{q \log(n)}{n}}$ entails that, with probability larger than $1 - 4(q/n) - \beta(q)\sqrt{n/(\alpha q)}$,

$$ F(\hat{t}) \le \alpha - \delta + \sqrt{\frac{\alpha q}{n}} + 4\sqrt{\frac{q \log(n)}{n}} \sqrt{F(\hat{t})}, $$

which leads to

$$ \sqrt{F(\hat{t})} \le 2\sqrt{\frac{q \log(n)}{n}} + \sqrt{\alpha - \delta + \sqrt{\frac{\alpha q}{n}} + 4\frac{q \log(n)}{n}}. $$

Choosing $\delta \ge 4\sqrt{\alpha}\sqrt{\frac{q \log(n)}{n}} + \sqrt{\frac{\alpha q}{n}}$ ensures that the right-hand side is smaller than $\sqrt{\alpha}$. ■

### 7.2.5 PROOF OF LEMMA 13

**Proof** [Proof of Lemma 13] The proof follows the one of (Chazal et al., 2021, Lemma 22) verbatim, at the exception of the capacity bound, that we discuss now. To lighten notation we assume that we have a $n/(2q)$ sample of $Y_i$'s, with $Y_i = (Z_{(i-1)q+1}, \dots, Z_{iq}) \in \mathbb{R}^q$, and we consider the set of functionals

$$ \mathcal{F} = \left\{ y = (z_1, \dots, z_q) \mapsto \frac{1}{q} \sum_{i=1}^{q} 1_{z_i > t} \right\}. $$

Following (Chazal et al., 2021, Lemma 22), if $S_{\mathcal{F}}(y_1, \dots, y_{n/(2q)})$ denotes the cardinality of $\{f(y_1), \dots, f(y_{n/(2q)}) | f \in \mathcal{F}\}$, we have to bound

$$ S_{\mathcal{F}}(Y_1, \dots, Y_{n/(2q)}, Y'_1, \dots, Y'_{n/(2q)}), $$
*Proceedings of The 24th International Conference on Artificial Intelligence and Statistics*, volume 130 of *Proceedings of Machine Learning Research*, pages 1000–1008. PMLR, 13–15 Apr 2021. URL https://proceedings.mlr.press/v130/royer21a.html.

S. Schmidl, P. Wenig, and T. Papenbrock. Anomaly detection in time series: A comprehensive evaluation. *Proceedings of the VLDB Endowment (PVLDB)*, 15(9):1779–1797, 2022. doi: 10.14778/3538598.3538602.

S. Sørbø and M. Ruocco. Navigating the metric maze: a taxonomy of evaluation metrics for anomaly detection in time series. *Data Mining and Knowledge Discovery*, pages 1–42, 11 2023. doi: 10.1007/s10618-023-00988-8.

C. Tang and C. Monteleoni. On lloyd's algorithm: New theoretical insights for clustering in practice. In A. Gretton and C. C. Robert, editors, *Proceedings of the 19th International Conference on Artificial Intelligence and Statistics*, volume 51 of *Proceedings of Machine Learning Research*, pages 1280–1289, Cadiz, Spain, 09–11 May 2016. PMLR. URL http://proceedings.mlr.press/v51/tang16b.html.

The GUDHI Project. *GUDHI User and Reference Manual*. GUDHI Editorial Board, 2015. URL http://gudhi.gforge.inria.fr/doc/latest/.

Y. Umeda, J. Kaneko, H. Kikuchi, and D. Kikuchi. Topological data analysis and its application to time-series data analysis. 2019. URL https://api.semanticscholar.org/CorpusID:225065707.

P. Wenig, S. Schmidl, and T. Papenbrock. Timeeval: A benchmarking toolkit for time series anomaly detection algorithms. *Proceedings of the VLDB Endowment (PVLDB)*, 15(12): 3678–3681, 2022. doi: 10.14778/3554821.3554873.

T. Yairi, Y. Kato, and K. Hori. Fault detection by mining association rules from house-keeping data. 2001.

Y. Zheng, H. Y. Koh, M. Jin, L. Chi, K. T. Phan, S. Pan, Y.-P. P. Chen, and W. Xiang. Correlation-aware spatial–temporal graph learning for multivariate time-series anomaly detection. *IEEE Transactions on Neural Networks and Learning Systems*, 2023.
where the $Y_i'$s are i.i.d. copies of the $Y_i$'s. Since, for every $y_1, \dots, y_{n/q}$, recalling that $y_i = (z_{(i-1)q+1}, \dots, z_{iq})$, it holds

$$S_{\mathcal{F}}(y_1, \dots, y_{n/q}) \le \{(1_{z_1>t}, \dots, 1_{z_n>t}) \mid t \in \mathbb{R}\},$$

we deduce that

$$S_{\mathcal{F}}(Y_1, \dots, Y_{n/(2q)}, Y'_1, \dots, Y'_{n/(2q)}) \le n.$$

The remaining of the proof follows verbatim (Chazal et al., 2021, Lemma 22). ■

## References

Henry Adams, Tegan Emerson, Michael Kirby, Rachel Neville, Chris Peterson, Patrick Shipman, Sofya Chepushtanova, Eric Hanson, Francis Motta, and Lori Ziegelmeier. Persistence images: a stable vector representation of persistent homology. *J. Mach. Learn. Res.*, 18:Paper No. 8, 35, 2017. ISSN 1532-4435.

Alekh Agarwal and John C. Duchi. The generalization ability of online algorithms for dependent data. *IEEE Trans. Inform. Theory*, 59(1):573–587, 2013. ISSN 0018-9448,1557-9654. doi: 10.1109/TIT.2012.2212414. URL https://doi.org/10.1109/TIT.2012.2212414.

Sylvain Arlot, Alain Celisse, and Zaid Harchaoui. A kernel multiple change-point algorithm via model selection. *J. Mach. Learn. Res.*, 20:Paper No. 162, 56, 2019. ISSN 1532-4435,1533-7928.

Jean-Daniel Boissonnat, Frédéric Chazal, and Mariette Yvinec. *Geometric and Topological Inference*, volume 57. Cambridge University Press, 2018.

Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: a survey of some recent advances. *ESAIM Probab. Stat.*, 9:323–375, 2005. ISSN 1292-8100,1262-3318. doi: 10.1051/ps:2005018. URL https://doi.org/10.1051/ps:2005018.

Anass El Yaagoubi Bourakna, Moo K. Chung, and Hernando Ombao. Modeling and simulating dependence in networks using topological data analysis, 2022.

Claire Brécheteau, Aurélie Fischer, and Clément Levrard. Robust Bregman clustering. *The Annals of Statistics*, 49(3):1679 – 1701, 2021. doi: 10.1214/20-AOS2018. URL https://doi.org/10.1214/20-AOS2018.

L Breiman. Random forests. 45:5–32, 2001-10. doi: 10.1023/A:1010950718922.

P. Bruillard, K. Nowak, and E. Purvine. Anomaly detection using persistent homology. In *2016 Cybersecurity Symposium (CYBERSEC)*, pages 7–12, Los Alamitos, CA, USA, apr 2016. IEEE Computer Society. doi: 10.1109/CYBERSEC.2016.009. URL https://doi.ieeecomputersociety.org/10.1109/CYBERSEC.2016.009.
Mathieu Carrière, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda. Perslay: A neural network layer for persistence diagrams and new graph topological signatures. In *International Conference on Artificial Intelligence and Statistics*, pages 2786–2796. PMLR, 2020.

Frédéric Chazal and Vincent Divol. The density of expected persistence diagrams and its kernel based estimation. In *34th International Symposium on Computational Geometry*, volume 99 of *LIPIcs. Leibniz Int. Proc. Inform.*, pages Art. No. 26, 15. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018.

Frédéric Chazal and Bertrand Michel. An introduction to topological data analysis: fundamental and practical aspects for data scientists. *Frontiers in artificial intelligence*, 4:108, 2021.

Frédéric Chazal, Vin de Silva, and Steve Oudot. Persistence stability for geometric complexes. *Geometriae Dedicata*, 173(1):193–214, 2014.

Frédéric Chazal, Vin de Silva, Marc Glisse, and Steve Oudot. *The structure and stability of persistence modules*. Springer International Publishing, 2016.

Frédéric Chazal, Clément Levrard, and Martin Royer. Clustering of measures via mean measure quantization. *Electronic Journal of Statistics*, 15(1):2060 – 2104, 2021. doi: 10.1214/21-EJS1834. URL https://doi.org/10.1214/21-EJS1834.

Stéphane Chrétien, Ben Gao, Astrid Thebault-Guiochon, and Rémi Vaucher. Time topological analysis of eeg using signature theory, 2024.

Meryll Dindin, Yuhei Umeda, and Frederic Chazal. Topological data analysis for arrhythmia detection through modular neural networks, 2019.

Vincent Divol and Frédéric Chazal. The density of expected persistence diagrams and its kernel based estimation. *Journal of Computational Geometry*, 10(2):127–153, 2019.

P. Doukhan, P. Massart, and E. Rio. Invariance principles for absolutely regular empirical processes. *Ann. Inst. H. Poincaré Probab. Statist.*, 31(2):393–427, 1995. ISSN 0246-0203. URL http://www.numdam.org/item?id=AIHPB_1995__31_2_393_0.

Paul Doukhan. *Mixing*, volume 85 of *Lecture Notes in Statistics*. Springer-Verlag, New York, 1994. ISBN 0-387-94214-9. doi: 10.1007/978-1-4612-2642-0. URL https://doi.org/10.1007/978-1-4612-2642-0. Properties and examples.

Herbert Edelsbrunner and John Harer. *Computational topology: an introduction*. American Mathematical Society, 2010.

Petri G., Expert P., Turkheimer F., Carhart-Harris R., Nutt D., Hellyer P.J., and Vaccarino F. Homological scaffolds of brain functional networks. *Journal of the Royal Society Interface*, 11(101), 2014. doi: 10.1098/rsif.2014.0873.

Niklas Heim and James E. Avery. Adaptive anomaly detection in chaotic time series with a spatially aware echo state network. *ArXiv*, abs/1909.01709, 2019. URL https://api.semanticscholar.org/CorpusID:202541761.
Steffen Herbold. Autorank: A python package for automated ranking of classifiers. *Journal of Open Source Software*, 5(48):2173, 2020. doi: 10.21105/joss.02173. URL https://doi.org/10.21105/joss.02173.

Thi Kieu Khanh Ho, Ali Karami, and Narges Armanfard. Graph-based time-series anomaly detection: A survey. *arXiv preprint arXiv:2302.00058*, 2023.

Christoph D Hofer, Roland Kwitt, and Marc Niethammer. Learning representations of persistence barcodes. *Journal of Machine Learning Research*, 20(126):1–45, 2019.

Mia Hubert, Michiel Debruyne, and Peter J. Rousseeuw. Minimum covariance determinant and extensions. *Wiley Interdiscip. Rev. Comput. Stat.*, 10(3):e1421, 11, 2018. ISSN 1939-5108,1939-0068. doi: 10.1002/wics.1421. URL https://doi.org/10.1002/wics.1421.

Vincent Jacob, Fei Song, Arnaud Stiegler, Bijan Rad, Yanlei Diao, and Nesime Tatbul. Exathlon: a benchmark for explainable anomaly detection over time series. 14(11): 2613–2626, 2021-07. ISSN 2150-8097. doi: 10.14778/3476249.3476307. URL https://doi.org/10.14778/3476249.3476307.

Soham Jana, Jianqing Fan, and Sanjeev Kulkarni. A general theory for robust clustering via trimmed mean, 2024.

Clément Levrard. Nonasymptotic bounds for vector quantization in hilbert spaces. *Ann. Statist.*, 43(2):592–619, 04 2015. doi: 10.1214/14-AOS1293. URL https://doi.org/10.1214/14-AOS1293.

Clément Levrard. Quantization/clustering: when and why does k-means work. *Journal de la Société Française de Statistiques*, 159(1), 2018.

Shuya Li, Wenbin Song, Chao Zhao, Yifeng Zhang, Weiming Shen, Jing Hai, Jiawei Lu, and Yingshi Xie. An anomaly detection method for multiple time series based on similarity measurement and louvain algorithm. *Procedia Computer Science*, 200:1857–1866, 2022.

Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. Isolation forest. In *2008 Eighth IEEE International Conference on Data Mining*, pages 413–422, 2008. doi: 10.1109/ICDM.2008.17.

Hendrik P. Lopuhaa and Peter J. Rousseeuw. Breakdown Points of Affine Equivariant Estimators of Multivariate Location and Covariance Matrices. *The Annals of Statistics*, 19(1):229–248, 1991. doi: 10.1214/aos/1176347978. URL https://doi.org/10.1214/aos/1176347978.

Daniel J. McDonald, Cosma Rohilla Shalizi, and Mark Schervish. Estimating beta-mixing coefficients via histograms. *Electron. J. Stat.*, 9(2):2855–2883, 2015. ISSN 1935-7524. doi: 10.1214/15-EJS1094. URL https://doi.org/10.1214/15-EJS1094.

Ahmed Hossam Mohammed, Mercedes Cabrerizo, Alberto Pinzon, Ilker Yaylali, Prasanna Jayakar, and Malek Adjouadi. Graph neural networks in eeg spike detection. *Artificial Intelligence in Medicine*, 145:102663, 2023. ISSN 0933-3657. doi: https://doi.org/10.1016/
j.artmed.2023.102663. URL https://www.sciencedirect.com/science/article/pii/S093336572300177X.

Mehryar Mohri and Afshin Rostamizadeh. Stability bounds for stationary φ-mixing and β-mixing processes. *J. Mach. Learn. Res.*, 11:789–814, 2010. ISSN 1532-4435,1533-7928.

Hernando Ombao and Marco Pinto. Spectral dependence, 2021.

John Paparrizos, Paul Boniol, Themis Palpanas, Ruey S. Tsay, Aaron Elmore, and Michael J. Franklin. Volume under the surface: a new accuracy evaluation measure for time-series anomaly detection. *Proc. VLDB Endow.*, 15(11):2774–2787, jul 2022a. ISSN 2150-8097. doi: 10.14778/3551793.3551830. URL https://doi.org/10.14778/3551793.3551830.

John Paparrizos, Yuhao Kang, Paul Boniol, Ruey S. Tsay, Themis Palpanas, and Michael J. Franklin. Tsb-uad: an end-to-end benchmark suite for univariate time-series anomaly detection. *Proc. VLDB Endow.*, 15(8):1697–1711, apr 2022b. ISSN 2150-8097. doi: 10.14778/3529337.3529354. URL https://doi.org/10.14778/3529337.3529354.

F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. *Journal of Machine Learning Research*, 12:2825–2830, 2011.

Tuan D. Pham and Lanh T. Tran. Some mixing properties of time series models. *Stochastic Process. Appl.*, 19(2):297–303, 1985. ISSN 0304-4149,1879-209X. doi: 10.1016/0304-4149(85)90031-6. URL https://doi.org/10.1016/0304-4149(85)90031-6.

Yu. V. Prokhorov. Convergence of random processes and limit theorems in probability theory. *Teor. Veroyatnost. i Primenen.*, 1:177–238, 1956. ISSN 0040-361X.

Nalini Ravishanker and Renjie Chen. Topological data analysis (tda) for time series, 2019.

Ian W. Renner, Jane Elith, Adrian Baddeley, William Fithian, Trevor Hastie, Steven J. Phillips, Gordana Popovic, and David I. Warton. Point process models for presence-only analysis. *Methods in Ecology and Evolution*, 6(4):366–379, 2015. doi: 10.1111/2041-210X.12352. URL https://besjournals.onlinelibrary.wiley.com/doi/abs/10.1111/2041-210X.12352.

Emmanuel Rio. Covariance inequalities for strongly mixing processes. *Ann. Inst. H. Poincaré Probab. Statist.*, 29(4):587–597, 1993. ISSN 0246-0203. URL http://www.numdam.org/item?id=AIHPB_1993__29_4_587_0.

Peter J. Rousseeuw and Katrien Van Driessen. A fast algorithm for the minimum covariance determinant estimator. *Technometrics*, 41(3):212–223, 1999. doi: 10.1080/00401706.1999.10485670. URL https://www.tandfonline.com/doi/abs/10.1080/00401706.1999.10485670.

Martin Royer, Frederic Chazal, Clément Levrard, Yuhei Umeda, and Yuichi Ike. Atol: Measure vectorization for automatic topologically-oriented learning. In Arindam Banerjee and Kenji Fukumizu, editors, *Proceedings of The 24th International Conference on*
*Artificial Intelligence and Statistics*, volume 130 of *Proceedings of Machine Learning Research*, pages 1000–1008. PMLR, 13–15 Apr 2021. URL https://proceedings.mlr.press/v130/royer21a.html.

Sebastian Schmidl, Phillip Wenig, and Thorsten Papenbrock. Anomaly detection in time series: A comprehensive evaluation. *Proceedings of the VLDB Endowment (PVLDB)*, 15 (9):1779–1797, 2022. doi: 10.14778/3538598.3538602.

Sondre Sørbø and Massimiliano Ruocco. Navigating the metric maze: a taxonomy of evaluation metrics for anomaly detection in time series. *Data Mining and Knowledge Discovery*, pages 1–42, 11 2023. doi: 10.1007/s10618-023-00988-8.

Cheng Tang and Claire Monteleoni. On Lloyd's algorithm: New theoretical insights for clustering in practice. In Arthur Gretton and Christian C. Robert, editors, *Proceedings of the 19th International Conference on Artificial Intelligence and Statistics*, volume 51 of *Proceedings of Machine Learning Research*, pages 1280–1289, Cadiz, Spain, 09–11 May 2016. PMLR. URL http://proceedings.mlr.press/v51/tang16b.html.

The GUDHI Project. *GUDHI User and Reference Manual*. GUDHI Editorial Board, 2015. URL http://gudhi.gforge.inria.fr/doc/latest/.

Yuhei Umeda, Junji Kaneko, Hideyuki Kikuchi, and Dr. Kikuchi. Topological data analysis and its application to time-series data analysis. 2019. URL https://api.semanticscholar.org/CorpusID:225065707.

Phillip Wenig, Sebastian Schmidl, and Thorsten Papenbrock. Timeeval: A benchmarking toolkit for time series anomaly detection algorithms. *Proceedings of the VLDB Endowment (PVLDB)*, 15(12):3678–3681, 2022. doi: 10.14778/3554821.3554873.

Weichen Wu, Jisu Kim, and Alessandro Rinaldo. On the estimation of persistence intensity functions and linear representations of persistence diagrams. In *International Conference on Artificial Intelligence and Statistics*, pages 3610–3618. PMLR, 2024.

Takehisa Yairi, Yoshikiyo Kato, and Koichi Hori. Fault detection by mining association rules from house-keeping data. 2001.

Yu Zheng, Huan Yee Koh, Ming Jin, Lianhua Chi, Khoa T Phan, Shirui Pan, Yi-Ping Phoebe Chen, and Wei Xiang. Correlation-aware spatial–temporal graph learning for multivariate time-series anomaly detection. *IEEE Transactions on Neural Networks and Learning Systems*, 2023.