### B.5. From $\Delta_{\Pi}(\theta)$ to $R_{\Pi}(\theta)$

Lemma B.2 strongly suggests studying a certain fraction involving $\Delta_{\Pi}(\theta)$. In the following result, we boil it down to a function of the residual term $R_{\Pi}(\theta)$.

**Lemma B.3.** Assume $\|R(\theta)\|_2 \le (\sigma^2 + \omega^2)/2$. We have the following upper bound:

$$ \frac{\|\Delta_{\Pi}(\theta)\|_F^2}{2(1 + \lambda_{\min}(\Delta_{\Pi}(\theta)))} \le \frac{\|R_{\Pi}(\theta)\|_F^2}{(\sigma^2 + \omega^2)^2}. $$

*Proof.* Since the quantity $\lambda_{\min}(\Delta_{\Pi}(\theta))$ in the denominator is hard to control, we will work with the spectral norm instead. Indeed, whenever $\|\Delta_{\Pi}(\theta)\|_2 < 1$, we have the crude bound $\frac{1}{1-\lambda_{\min}(\Delta_{\Pi}(\theta))} \le \frac{1}{1-\|\Delta_{\Pi}(\theta)\|_2}$. Let us start by noticing that, thanks to Lemma C.3,

$$ \begin{aligned} \|\Delta_{\Pi}(\theta)\|_F^2 &= \|Q_{\Pi}^{-1/2} R_{\Pi}(\theta) Q_{\Pi}^{-1/2}\|_F^2 \le \|Q_{\Pi}^{-1/2}\|_2^4 \|R_{\Pi}(\theta)\|_F^2 = \|Q_{\Pi}^{-1}\|_2^2 \|R_{\Pi}(\theta)\|_F^2 \\ \|\Delta_{\Pi}(\theta)\|_2 &= \|Q_{\Pi}^{-1/2} \Pi R_{\Pi}(\theta) \Pi' Q_{\Pi}^{-1/2}\|_2 \le \|Q_{\Pi}^{-1/2} \Pi\|_2^2 \|R(\theta)\|_2. \end{aligned} $$

We will later see how the spectral and Frobenius norms of the residual $R(\theta)$ can be controlled as a function of $\theta$. For now, we must work to upper bound $\|Q_{\Pi}^{-1}\|_2$ and $\|Q_{\Pi}^{-1}\Pi\|_2^2$.

Since we assumed $E^c$ happens (non-empty projection), we have $\Pi\Pi' = I$ and $\Pi'\Pi = \text{diag}(\pi)$, which has at least one entry equal to 1.

We start with $\|Q_{\Pi}^{-1}\|_2$:

$$ \begin{aligned} \|Q_{\Pi}^{-1}\|_2 &= \lambda_{\max}(Q_{\Pi}^{-1}) = \frac{1}{\sigma^2 + \omega^2} \\ \|Q_{\Pi}^{-1/2} \Pi\|_2^2 &= \lambda_{\max}(\Pi' Q_{\Pi}^{-1} \Pi) = \frac{1}{\sigma^2 + \omega^2} \lambda_{\max}(\Pi' \Pi) = \frac{1}{\sigma^2 + \omega^2}. \end{aligned} $$

The conclusion is within reach:

$$ \begin{aligned} \frac{\|\Delta_{\Pi}(\theta)\|_F^2}{1 + \lambda_{\min}(\Delta_{\Pi}(\theta))} &\le \frac{\|\Delta_{\Pi}(\theta)\|_F^2}{1 - \|\Delta_{\Pi}(\theta)\|_2} \le \frac{\|Q_{\Pi}^{-1}\|_2^2 \|R_{\Pi}(\theta)\|_F^2}{1 - \|Q_{\Pi}^{-1/2} \Pi\|_2^2 \|R(\theta)\|_2} \\ &= \frac{\left(\frac{1}{\sigma^2 + \omega^2}\right)^2 \|R_{\Pi}(\theta)\|_F^2}{1 - \frac{1}{\sigma^2 + \omega^2} \|R(\theta)\|_2^2} \le \frac{2 \|R_{\Pi}(\theta)\|_F^2}{(\sigma^2 + \omega^2)^2} \end{aligned} $$

The last inequality is justified by our assumption $\|R(\theta)\|_2 \le (\sigma^2 + \omega^2)/2$. Another consequence of this assumption is that

$$ \|\Delta_{\Pi}(\theta)\|_2 \le \|Q_{\Pi}^{-1/2} \Pi\|_2^2 \|R(\theta)\|_2 \le \frac{1}{\sigma^2 + \omega^2} \frac{\sigma^2 + \omega^2}{2} = \frac{1}{2} < 1 $$

which is sufficient for the first inequality to hold. □

### B.6. From $R_{\Pi}(\theta)$ to $R(\theta)$

As the previous Lemma underlines, the last step we need to get rid of the dependency in $\Pi$ is to study the average norm of $R_{\Pi}(\theta)$.

**Lemma B.4.** We have $\mathbb{E}_{\Pi} [1_{E^c} \|R_{\Pi}(\theta)\|_F^2] \le p \text{Tr}[R(\theta) \odot R(\theta)] + p^2 \|R(\theta)\|_F^2$.
Proof. We start by giving a formula for the blocks of $R(\theta)$: by Lemma 16,

$$R(\theta)_{[t,s]} = \begin{cases} \theta^{t-s} \Gamma_0(\theta) & \text{if } s \in [1, t-1] \\ \theta \Gamma_0(\theta) \theta' & \text{if } s = t \\ \Gamma_0(\theta) \theta^{t-s} & \text{if } s \in [t+1, T]. \end{cases}$$

These individual blocks can be bounded using Lemmas 25 and 2: if $r \ge 1$, then

$$\|\theta^r \Gamma_0(\theta)\|_F^2 \le \|\Gamma_0(\theta)\|_2^2 \|\theta^r\|_F^2 \le \|\Gamma_0(\theta)\|_2^2 \|\theta\|_F^2 \|\theta^{r-1}\|_2^2 \le \frac{\sigma_{\max}^4}{(1-\vartheta)^2} \|\theta\|_F^2 \|\theta\|_2^{2(r-1)}$$

$$\|\Gamma_0(\theta)\theta'^r\|_F^2 \le \|\Gamma_0(\theta)\|_2^2 \|\theta^r\|_F^2 \le \|\Gamma_0(\theta)\|_2^2 \|\theta\|_F^2 \|\theta^{r-1}\|_2^2 \le \frac{\sigma_{\max}^4}{(1-\vartheta)^2} \|\theta\|_F^2 \|\theta\|_2^{2(r-1)}$$

$$\|\theta \Gamma_0(\theta) \theta'\|_F^2 \le \|\theta\|_2^2 \|\Gamma_0(\theta)\|_2^2 \|\theta\|_F^2 \le \frac{\sigma_{\max}^4}{(1-\vartheta)^2} \|\theta\|_F^2 \|\theta\|_2^2.$$

Since we control the norm of each block of $R(\theta)$, we control the norm of the whole matrix:

$$\begin{aligned} \|R(\theta)\|_F^2 &= \sum_{t=1}^{T} \left( \sum_{s=1}^{t-1} \|\theta^{t-s} \Gamma_0(\theta)\|_F^2 + \|\theta \Gamma_0(\theta) \theta\|_F^2 + \sum_{s=t+1}^{T} \|\Gamma_0(\theta) \theta^{s-t}\|_F^2 \right) \\ &\le \frac{\sigma_{\max}^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} \sum_{t=1}^{T} \left( \sum_{s=1}^{t-1} \|\theta\|_2^{2(t-s-1)} + \|\theta\|_2^2 + \sum_{s=t+1}^{T} \|\theta\|_2^{2(s-t-1)} \right) \\ &\le \frac{\sigma_{\max}^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} \sum_{t=1}^{T} \left( \sum_{s=-\infty}^{t-1} \|\theta\|_2^{2(t-1-s)} + \|\theta\|_2^2 + \sum_{s=t+1}^{+\infty} \|\theta\|_2^{2(s-1-t)} \right) \\ &= \frac{\sigma_{\max}^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} T \left( \frac{1}{1-\|\theta\|_2^2} + \|\theta\|_2^2 + \frac{1}{1-\|\theta\|_2^2} \right) \end{aligned}$$

We now remember our hypothesis $\|\theta\|_2 \le \vartheta < 1$:

$$\begin{aligned} \|R(\theta)\|_F^2 &\le \frac{\sigma_{\max}^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} T \left( \frac{1}{1-\vartheta^2} + \vartheta^2 + \frac{1}{1-\vartheta^2} \right) \\ &= \frac{\sigma_{\max}^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} T \left( \frac{2+\vartheta^2(1-\vartheta^2)}{1-\vartheta^2} \right) \\ &\le \frac{\sigma_{\max}^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} T \left( \frac{2+2\vartheta}{1-\vartheta^2} \right) = \frac{\sigma_{\max}^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} T \left( \frac{2}{1-\vartheta} \right) \\ &= 2T \frac{\sigma_{\max}^4 \|\theta\|_F^2}{(1-\vartheta)^3}. \end{aligned}$$

Now that we have a handle on the Frobenius norm of $R(\theta)$, we move on to its spectral norm. Notice that $R(\theta)$ can be written as a sum of Kronecker products with the subdiagonal matrices $J_t$:

$$R(\theta) = I \otimes \theta \Gamma_0(\theta) \theta' + \sum_{t=1}^{T-1} [J_t \otimes \theta^t \Gamma_0(\theta) + J'_t \otimes \Gamma_0(\theta) \theta'^t].$$
*Proof.* We first notice that for any matrix A,

$$ 
\begin{aligned}
\mathbb{E}_{\Pi}[\mathbf{1}_{E^c} \|\Pi A \Pi'\|_F^2] &= \mathbb{E}_{\Pi}[\mathbf{1}_{E^c} \operatorname{Tr}[\Pi A \Pi' \Pi A' \Pi')] \\
&= \mathbb{E}_{\Pi}[\operatorname{Tr}[\operatorname{diag}(\pi) A \operatorname{diag}(\pi) A']]
\end{aligned}
$$
$$= \sum_{i,j} \mathbb{E}_{\Pi}[\pi_i \pi_j] A_{i,j}^2$$

We can apply this to $R_{\Pi}(\theta) = \Pi R(\theta) \Pi'$:

$$ \mathbb{E}_{\Pi}[\mathbf{1}_{E^c} \|R_{\Pi}(\theta)\|_F^2] = \sum_{i,j} \mathbb{E}_{\Pi}[\pi_i \pi_j] R(\theta)_{i,j}^2. $$

The rest of the proof consists in plugging in the moments $\mathbb{E}_{\Pi}[\pi_i \pi_j]$ from Lemma A.4:

$$ 
\begin{aligned}
\mathbb{E}_{\Pi}[\mathbf{1}_{E^c} \|R_{\Pi}(\theta)\|_F^2] &= \sum_{\substack{t_1,t_2,d_1,d_2 \\ (t_1,d_1)=(t_2,d_2)}} pR(\theta)_{(t_1,d_1),(t_2,d_2)}^2 \\
&\quad + \sum_{\substack{t_1,t_2,d_1,d_2 \\ (t_1,d_1) \neq (t_2,d_2)}} p^2 R(\theta)_{(t_1,d_1),(t_2,d_2)}^2
\end{aligned}
$$

The first sum is easy to handle with the trace:

$$ 
\begin{aligned}
\sum_{\substack{t_1,t_2,d_1,d_2 \\ (t_1,d_1)=(t_2,d_2)}} pR(\theta)_{(t_1,d_1),(t_2,d_2)}^2 &= \sum_{t,d} pR(\theta)_{(t,d),(t,d)}^2 \\
&\le p \operatorname{Tr}[R(\theta) \odot R(\theta)]
\end{aligned}
$$

The second sum is almost the Frobenius norm:

$$ \sum_{\substack{t_1,t_2,d_1,d_2 \\ (t_1,d_1) \neq (t_2,d_2)}} p^2 R(\theta)_{(t_1,d_1),(t_2,d_2)}^2 \le p^2 \|R(\theta)\|_F^2 $$

This yields the expected bound.

□

### B.7. Bounding $R(\theta)$

Lemma B.4 relates the bounds involving $R_{\Pi}(\theta)$ to features of the full residual $R(\theta)$, which we now study.

**Lemma B.5.** The residual $R(\theta)$ satisfies the following inequalities:

$$ \|R(\theta)\|_2 \le \frac{2\sigma^2}{(1-\vartheta)^2} \|\theta\|_2 $$

$$ \|R(\theta)\|_F^2 \le \frac{2T\sigma^4}{(1-\vartheta)^3} \|\theta\|_F^2 $$

$$ \operatorname{Tr}[R(\theta) \odot R(\theta)] \le \frac{T\sigma^4}{(1-\vartheta)^2} \|\theta\|_2^2 \|\theta\|_F^2. $$
We can use Lemma 24 and write:

$$
\begin{align*}
\|R(\theta)\|_2 &\le \|I\|_2 \times \|\theta\Gamma_0(\theta)\theta'\|_2 + \sum_{t=1}^{T-1} [\|J_t\|_2 \times \|\theta^t\Gamma_0(\theta)\|_2 + \|J'_t\|_2 \times \|\Gamma_0(\theta)\theta''\|_2] \\
&\le \|\Gamma_0(\theta)\|_2 \left( \|\theta\|_2^2 + 2 \sum_{t=1}^{T-1} \|\theta\|_2^t \right) \le \frac{\sigma_{\max}^2}{1-\vartheta^2} \left( \|\theta\|_2^2 + 2 \frac{\|\theta\|_2}{1-\|\theta\|_2} \right) \\
&\le \frac{\sigma_{\max}^2 \|\theta\|_2}{1-\vartheta^2} \left( \vartheta + \frac{2}{1-\vartheta} \right) \le \frac{\sigma_{\max}^2 \|\theta\|_2}{1-\vartheta} \left( \frac{2+2\vartheta}{1-\vartheta^2} \right) \\
&= 2 \frac{\sigma_{\max}^2 \|\theta\|_2}{(1-\vartheta)^2}.
\end{align*}
$$

We finish with the trace of the Hadamard product $R(\theta) \odot R(\theta)$.

$$
\begin{align*}
\operatorname{Tr}[R(\theta) \odot R(\theta)] &= T \operatorname{Tr}[(\theta \Gamma_0(\theta) \theta') \odot (\theta \Gamma_0(\theta) \theta')] \\
&\le T \|\theta \Gamma_0(\theta) \theta'\|_F^2 \le T \sigma_{\max}^4 \frac{\|\theta\|_2^2 \|\theta\|_F^2}{(1 - \vartheta)^2}.
\end{align*}
$$

□

B.8 UPPER BOUND ON THE KL DIVERGENCE

We now have all the tools in hand to extract a KL divergence bound.

**Lemma 21 (Final KL bound).** *Assume $\theta \in \Theta_s$ satisfies*

$$
\|\theta\|_2 \le \frac{(1 - \vartheta)^2 (\sigma_{\min}^2 + \omega^2)}{4\sigma_{\max}^2}
$$

then the expected conditional KL divergence is upper-bounded as follows:

$$
\mathbb{E}_{\Pi} [\mathrm{KL} \{ \mathbb{P}_{\theta}(Y|\Pi) \| \mathbb{P}_{0}(Y|\Pi) \}] \leq \mathrm{KL}_{\mathrm{avg}} (\|\theta\|_{2}, \|\theta\|_{F})
$$

where we defined

$$
\gamma_{\ell} = (1 - \vartheta)^{3/2} \frac{\sigma_{\min}^2 + \omega^2}{\sigma_{\max}^2} \quad \text{and} \quad \mathrm{KL}_{\mathrm{avg}}(\|\theta\|_2, \|\theta\|_F) = \frac{2Tp(\|\theta\|_2^2 + q_{\ell})\|\theta\|_F^2}{\gamma_{\ell}}.
$$

*Proof.* Let us start with Lemma 17 on the conditional KL divergence between $\mathbb{P}_{\theta}(Y|\Pi)$ and $\mathbb{P}_{0}(Y|\Pi)$: for any non-empty $\Pi$,

$$
\mathrm{KL} \{ \mathbb{P}_{\theta}(Y|\Pi) \| \mathbb{P}_{0}(Y|\Pi) \} \leq \frac{\| \Delta_{\Pi}(\theta) \|_{F}^{2}}{2(1 + \lambda_{\min}(\Delta_{\Pi}(\theta)))}
$$

We continue with Lemma 18 linking $\Delta_{\Pi}(\theta)$ to $R_{\Pi}(\theta)$. As long as $\|R(\theta)\|_2 \le (\sigma_{\min}^2 + \omega^2)/2$ (we will see to that at the end), we have

$$
\mathrm{KL} \{ \mathbb{P}_{\theta}(Y|\Pi) \| \mathbb{P}_{0}(Y|\Pi) \} \leq \frac{\| R_{\Pi}(\theta) \|_{F}^{2}}{(\sigma_{\min}^{2} + \omega^{2})^{2}}.
$$

Taking the expectation on the event $E^c$ yields:

$$
\mathbb{E}_{\Pi} [\mathbf{1}_{E^c} \mathrm{KL} \{ \mathbb{P}_{\theta}(Y|\Pi) \| \mathbb{P}_{0}(Y|\Pi) \}] \leq \frac{\mathbb{E}_{\Pi} [\mathbf{1}_{E^c} \| R_{\Pi}(\theta) \|_{F}^{2}]}{(\sigma_{\min}^{2} + \omega^{2})^{2}}
$$

We can now apply Lemma 19:

$$
\mathbb{E}_{\Pi} [\mathbf{1}_{E^c} \mathrm{KL} \{ \mathbb{P}_{\theta}(Y|\Pi) \| \mathbb{P}_{0}(Y|\Pi) \}] \le \frac{p \mathrm{Tr}[R(\theta) \odot R(\theta)] + pq_{\ell} \|R(\theta)\|_{F}^{2}}{(\sigma_{\min}^{2} + \omega^{2})^{2}}
$$
*Proof.* We start by giving a formula for the blocks of $R(\theta)$: by Lemma B.1,

$$ R(\theta)_{[t,s]} = \begin{cases} \theta^{t-s} \Gamma_0(\theta) & \text{if } s \in [1, t-1] \\ \theta \Gamma_0(\theta) \theta' & \text{if } s = t \\ \Gamma_0(\theta) \theta^{t-s} & \text{if } s \in [t+1, T]. \end{cases} $$

These individual blocks can be bounded using Lemmas C.3 and A.2: if $r \ge 1$, then

$$ \|\theta^r \Gamma_0(\theta)\|_F^2 \le \|\Gamma_0(\theta)\|_2^2 \|\theta^r\|_F^2 \le \|\Gamma_0(\theta)\|_2^2 \|\theta\|_F^2 \|\theta^{r-1}\|_2^2 \le \frac{\sigma^4}{(1-\vartheta)^2} \|\theta\|_F^2 \|\theta\|_2^{2(r-1)} $$

$$ \|\Gamma_0(\theta)\theta''\|_F^2 \le \|\Gamma_0(\theta)\|_2^2 \|\theta''\|_F^2 \le \|\Gamma_0(\theta)\|_2^2 \|\theta\|_F^2 \|\theta^{r-1}\|_2^2 \le \frac{\sigma^4}{(1-\vartheta)^2} \|\theta\|_F^2 \|\theta\|_2^{2(r-1)} $$

$$ \|\theta \Gamma_0(\theta) \theta''\|_F^2 \le \|\theta\|_2^2 \|\Gamma_0(\theta)\|_2^2 \|\theta\|_F^2 \le \frac{\sigma^4}{(1-\vartheta)^2} \|\theta\|_F^2 \|\theta\|_2^2. $$

Since we control the norm of each block of $R(\theta)$, we control the norm of the whole matrix:

$$ \begin{aligned} \|R(\theta)\|_F^2 &= \sum_{t=1}^{T} \left( \sum_{s=1}^{t-1} \|\theta^{t-s} \Gamma_0(\theta)\|_F^2 + \|\theta \Gamma_0(\theta) \theta\|_F^2 + \sum_{s=t+1}^{T} \|\Gamma_0(\theta) \theta^{s-t}\|_F^2 \right) \\ &\le \frac{\sigma^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} \sum_{t=1}^{T} \left( \sum_{s=1}^{t-1} \|\theta\|_2^{2(t-s-1)} + \|\theta\|_2^2 + \sum_{s=t+1}^{T} \|\theta\|_2^{2(s-t-1)} \right) \\ &\le \frac{\sigma^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} \sum_{t=1}^{T} \left( \sum_{s=-\infty}^{t-1} \|\theta\|_2^{2(t-1-s)} + \|\theta\|_2^2 + \sum_{s=t+1}^{+\infty} \|\theta\|_2^{2(s-1-t)} \right) \\ &= \frac{\sigma^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} T \left( \frac{1}{1-\|\theta\|_2^2} + \|\theta\|_2^2 + \frac{1}{1-\|\theta\|_2^2} \right) \end{aligned} $$

We now remember our hypothesis $\|\theta\|_2 \le \vartheta < 1$:

$$ \begin{aligned} \|R(\theta)\|_F^2 &\le \frac{\sigma^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} T \left( \frac{1}{1-\vartheta^2} + \vartheta^2 + \frac{1}{1-\vartheta^2} \right) \\ &= \frac{\sigma^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} T \left( \frac{2+\vartheta^2(1-\vartheta^2)}{1-\vartheta^2} \right) \\ &\le \frac{\sigma^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} T \left( \frac{2+2\vartheta}{1-\vartheta^2} \right) = \frac{\sigma^4 \|\theta\|_F^2}{(1-\vartheta^2)^2} T \left( \frac{2}{1-\vartheta} \right) \\ &= 2T \frac{\sigma^4 \|\theta\|_F^2}{(1-\vartheta)^3}. \end{aligned} $$

Now that we have a handle on the Frobenius norm of $R(\theta)$, we move on to its spectral norm. Notice that $R(\theta)$ can be written as a sum of Kronecker products with the subdiagonal matrices $J_t$:

$$ R(\theta) = I \otimes \theta \Gamma_0(\theta) \theta' + \sum_{t=1}^{T-1} [J_t \otimes \theta^t \Gamma_0(\theta) + J'_t \otimes \Gamma_0(\theta) \theta'^t]. $$
We substitute the residual bounds from Lemma 20:

$$
\begin{align*}
\mathbb{E}_{\Pi} [\mathbf{1}_{E^c} \text{KL} \{\mathbb{P}_{\theta}(Y|\Pi) \parallel \mathbb{P}_0(Y|\Pi)\}] &\le \frac{p \times \frac{T \sigma_{\max}^4}{(1-\vartheta)^2} \|\theta\|_2^2 \|\theta\|_F^2 + pq_{\ell} \times \frac{2T \sigma_{\max}^4}{(1-\vartheta)^3} \|\theta\|_F^2}{(\sigma_{\min}^2 + \omega^2)^2} \\
&\le \left( \frac{\sigma_{\max}^2}{\sigma_{\min}^2 + \omega^2} \right)^2 \frac{2Tp(\|\theta\|_2^2 + q_{\ell}) \|\theta\|_F^2}{(1-\vartheta)^3} \\
&= \frac{2Tp(\|\theta\|_2^2 + q_{\ell}) \|\theta\|_F^2}{\gamma_{\ell}}.
\end{align*}
$$

By Equation (24), this is equivalent to bounding the expected KL divergence regardless of the event E, hence the
result. Note that our assumption on θ, combined with Lemma 20, implies

$$
\|R(\theta)\|_2 \le \frac{2\sigma_{\max}^2}{(1-\vartheta)^2} \|\theta\|_2 \le \frac{2\sigma_{\max}^2}{(1-\vartheta)^2} \frac{(1-\vartheta)^2(\sigma_{\min}^2 + \omega^2)}{4\sigma_{\max}^2} \le \frac{\sigma_{\min}^2 + \omega^2}{2}
$$

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

B.9 APPLICATION OF FANO’S METHOD

Given the KL bound we just obtained, we are finally able to prove Theorem 2.

Proof. Fano’s method requires finding $M+1$ parameters $\theta_i$ such that $\theta_0 = 0$ and $\|\theta_i - \theta_j\|_F \ge 2\tau$ for $i \ne j$ (with $\tau$ to be specified), while keeping control upon the average KL divergence between the probability distributions $\mathbb{P}_{\theta_i}$ and $\mathbb{P}_0$. Judging by Lemma 21, one way to achieve this control on the KL divergence is to bound the $\|\theta_i\|_F$ uniformly in $i$ (in other words, to choose them all inside a ball of fixed radius). We will then have to see how many $2\tau$-separated matrices we can fit in such a ball.

Let us consider the set $\mathcal{H}(r)$ of all block-diagonal $D \times D$ matrices with coefficients in $\{0, r\}$ such that each block has size $s \times s$ (we assume $s$ divides $D$). In particular, these matrices are all row- and column-sparse, with no more than $s$ non-zero coefficients per row or column. In terms of dimensionality, we are dealing with the (scaled) matrix equivalent of a $Ds$-dimensional hypercube, hence the notation $\mathcal{H}(r)$. It has cardinality $2^{Ds}$ and for every $\theta \in \mathcal{H}$, we have the following norm bounds:

$$
\|\theta\|_2 \le rs \quad \text{and} \quad \|\theta\|_F \le r\sqrt{Ds}.
$$

The spectral norm bound on $\theta$ is obtained as the maximum spectral norm of each block, which we in turn control using
the Frobenius norm of each block.

Unfortunately, in this hypercube, not all pairs of vertices are well-separated. That is why we need the Gilbert-
Varshamov bound of Lemma 35: according to this result, there exists a pruned subset $K(r) \subset \mathcal{H}(r)$ containing 0 and
such that

$$
|\mathcal{K}(r)| \ge |\mathcal{H}(r)|^{1/8} = 2^{Ds/8} \quad \text{and} \quad \|\mathrm{vec}(\theta_i) - \mathrm{vec}(\theta_j)\|_1 \ge \frac{rDs}{8}
$$

for all pairs of distinct vertices $\theta_i$ and $\theta_j$ in $\mathcal{K}(r)$. We choose our set of parameters $\theta_0, \theta_1, \dots, \theta_M$ to be exactly this
pruned subset $\mathcal{K}(r)$, in particular $M + 1 = |\mathcal{K}(r)|$.

The missing ingredient is an upper bound on the maximum average KL divergence between $\mathbb{P}_{\theta_i}$ and $\mathbb{P}_0$: we can
obtain it using Lemma 21. We only need to assume

$$
\|\theta_i\|_F \le r\sqrt{Ds} \le \min \left\{ \vartheta, \frac{(1-\vartheta)^2(\sigma_{\min}^2 + \omega^2)}{4\sigma_{\max}^2} \right\}
$$

to get the upper bound

$$
\begin{align*}
\max_i \mathbb{E}_{\Pi} [\text{KL} \{\mathbb{P}_{\theta_i}(Y|\Pi) \parallel \mathbb{P}_{\theta_0}(Y|\Pi)\}] &\le \max_i \text{KL}_{\text{avg}}(\|\theta_i\|_2, \|\theta_i\|_F) \\
&\le \text{KL}_{\text{avg}}(rs, r\sqrt{Ds}).
\end{align*}
$$
We can use Lemma C.2 and write:

$$
\begin{align*}
\|R(\theta)\|_2 &\le \|I\|_2 \times \|\theta\Gamma_0(\theta)\theta'\|_2 + \sum_{t=1}^{T-1} [\|J_t\|_2 \times \|\theta^t\Gamma_0(\theta)\|_2 + \|J'_t\|_2 \times \|\Gamma_0(\theta)\theta^{t'}\|_2] \\
&\le \|\Gamma_0(\theta)\|_2 \left( \|\theta\|_2^2 + 2 \sum_{t=1}^{T-1} \|\theta\|_2^t \right) \le \frac{\sigma^2}{1-\vartheta^2} \left( \|\theta\|_2^2 + 2 \frac{\|\theta\|_2}{1-\|\theta\|_2} \right) \\
&\le \frac{\sigma^2 \|\theta\|_2}{1-\vartheta^2} \left( \vartheta + \frac{2}{1-\vartheta} \right) \le \frac{\sigma^2 \|\theta\|_2}{1-\vartheta} \left( \frac{2+2\vartheta}{1-\vartheta^2} \right) \\
&= 2 \frac{\sigma^2 \|\theta\|_2}{(1-\vartheta)^2}.
\end{align*}
$$

We finish with the trace of the Hadamard product $R(\theta) \odot R(\theta)$.

$$
\begin{align*}
\mathrm{Tr}[R(\theta) \odot R(\theta)] &= T \mathrm{Tr}[(\theta\Gamma_0(\theta)\theta') \odot (\theta\Gamma_0(\theta)\theta')] \\
&\leq T \|\theta\Gamma_0(\theta)\theta'\|_F^2 \leq T \sigma^4 \frac{\|\theta\|_2^2 \|\theta\|_F^2}{(1-\vartheta)^2}. \quad \square
\end{align*}
$$

B.8. Upper bound on the KL divergence

We now have all the tools in hand to extract a KL divergence bound.

**Lemma B.6 (Final KL bound).** Assume $\theta \in \Theta_s$ satisfies $\|\theta\|_2 \le \frac{(1-\vartheta)^2(\sigma^2+\omega^2)}{4\sigma^2}$, then the expected conditional KL divergence is upper-bounded as follows:

$$
\mathbb{E}_{\Pi} [\mathrm{KL} \{ \mathbb{P}_{\theta}(Y|\Pi) \| \mathbb{P}_{0}(Y|\Pi) \}] \le \mathrm{KL}_{\mathrm{avg}} (\|\theta\|_{2}, \|\theta\|_{F})
$$

where we defined $\gamma_\ell = (1 - \vartheta)^{3/2} \frac{\sigma^2 + \omega^2}{\sigma^2}$ and $\mathrm{KL}_{\mathrm{avg}}(\|\theta\|_2, \|\theta\|_F) = \frac{2Tp(\|\theta\|_2^2+p)\|\theta\|_F^2}{\gamma_\ell}$.

*Proof.* Let us start with Lemma B.2 on the conditional KL divergence between $P_{\theta}(Y|\Pi)$ and $P_{0}(Y|\Pi)$: for any non-empty $\Pi$,

$$
\mathrm{KL} \{ \mathbb{P}_{\theta}(Y|\Pi) \| \mathbb{P}_{0}(Y|\Pi) \} \le \frac{\| \Delta_{\Pi}(\theta) \|_{F}^{2}}{2(1 + \lambda_{\min}(\Delta_{\Pi}(\theta)))}
$$

We continue with Lemma B.3 linking $\Delta_{\Pi}(\theta)$ to $R_{\Pi}(\theta)$. As long as $\|R(\theta)\|_2 \le (\sigma^2 + \omega^2)/2$ (we will see to that at the end), we have

$$
\mathrm{KL} \{ \mathbb{P}_{\theta}(Y|\Pi) \| \mathbb{P}_{0}(Y|\Pi) \} \le \frac{\| R_{\Pi}(\theta) \|_{F}^{2}}{(\sigma^{2} + \omega^{2})^{2}}.
$$

Taking the expectation on the event $E^c$ yields:

$$
\mathbb{E}_{\Pi} [\mathbf{1}_{E^c} \mathrm{KL} \{ \mathbb{P}_{\theta}(Y|\Pi) \| \mathbb{P}_{0}(Y|\Pi) \}] \le \frac{\mathbb{E}_{\Pi} [\mathbf{1}_{E^c} \| R_{\Pi}(\theta) \|_{F}^{2}]}{(\sigma^2 + \omega^2)^2}
$$

We can now apply Lemma B.4:

$$
\mathbb{E}_{\Pi} [\mathbf{1}_{E^c} \mathrm{KL} \{ \mathbb{P}_{\theta}(Y|\Pi) \| \mathbb{P}_{0}(Y|\Pi) \}] \le \frac{p \mathrm{Tr}[R(\theta) \odot R(\theta)] + p^2 \|R(\theta)\|_{F}^{2}}{(\sigma^2 + \omega^2)^2}
$$
Since we must satisfy the constraint from Equation (28) in Fano's method, we will choose $r$ so that:

$$KL_{\text{avg}}(rs, r\sqrt{Ds}) \leq \alpha \log(M) = \alpha \log(2^{Ds/8} - 1)$$

with $\alpha = \frac{\log 3 - \log 2}{2 \log 2}$. We want to solve the previous inequality for $r$, and for that we start by replacing $KL_{\text{avg}}(rs, r\sqrt{Ds})$ with its value from Lemma 21, replacing $\gamma_{\ell}$ with $\gamma_{\ell}$ to lighten notations:

$$\begin{align*}
KL_{\text{avg}}(rs, r\sqrt{Ds}) \leq \alpha \log (2^{Ds/8} - 1) &\iff \frac{2}{\gamma_{\ell}}Tp((rs)^2 + q_{\ell}) (r\sqrt{Ds})^2 \leq cDs \\
&\iff Ds^3r^4 + q_{\ell}Dsr^2 - c\frac{\gamma_{\ell}^2Ds}{Tpq_{\ell}} \leq 0.
\end{align*}$$

If we consider this as a degree two polynomial in the variable $r^2$, its determinant is

$$\Delta = q_{\ell}^2 D^2 s^2 + 4Ds^3 c \frac{\gamma_{\ell}^2 Ds}{Tp}.$$

For $\beta$ to be small enough, $r^2$ must remain below the only positive root of the polynomial, namely

$$r^2 \leq \frac{-q_{\ell}Ds + \sqrt{q_{\ell}^2 D^2 s^2 + c \frac{\gamma_{\ell}^2 D^2 s^4}{Tp}}}{2Ds^3} = \frac{q_{\ell}}{2s^2} \left( \sqrt{1 + c \frac{\gamma_{\ell}^2 s^2}{Tpq_{\ell}^2}} - 1 \right).$$

If we assume the quantity $c\frac{\gamma_{\ell}^2 s^2}{Tpq_{\ell}^2}$ inside the square root is smaller than 1, i.e.

$$\frac{\gamma_{\ell}s}{\sqrt{pq_{\ell}\sqrt{T}}} \leq c, \qquad (25)$$

then we can lower-bound $\sqrt{1+x}$ by its chord $(\sqrt{2}-1)x$. In other words, a sufficient condition for $r^2$ to remain small enough is given by

$$r^2 \leq \frac{q_{\ell}}{2s^2} \times (\sqrt{2} - 1) c \frac{\gamma_{\ell}^2 s^2}{Tpq_{\ell}^2} = c \frac{\gamma_{\ell}^2}{Tpq_{\ell}}.$$

To sum up, we have three constraints on $r$:

$$rs \leq \vartheta \qquad rs \leq \frac{(1-\vartheta)^2(\sigma_{\min}^2 + \omega^2)}{4\sigma_{\max}^2} = \frac{\sqrt{1-\vartheta}}{4}\gamma_{\ell} \qquad r \leq \sqrt{c\frac{\gamma_{\ell}^2}{Tpq_{\ell}}}.$$

We can therefore choose $r$ as the largest value satisfying all three of them:

$$r = \frac{1}{s} \min \left\{ \vartheta, \frac{\gamma_{\ell} \sqrt{1 - \vartheta}}{4}, c \frac{\gamma_{\ell} s}{\sqrt{Tpq_{\ell}}} \right\} \qquad (26)$$

To reach our conclusion, we simply need to remark that the vectorized $\ell_1$ distance between any two matrices in $\mathcal{K}(r)$ gives us a lower bound on the operator $\ell_{\infty}$ distance that separates them:

$$\begin{align*}
\|\theta_i - \theta_j\|_{\infty} &= \max_{k \in [D]} \sum_{l \in [D]} |(\theta_i - \theta_j)|_{k,l} \geq \frac{1}{D} \sum_{1 \leq k,l \leq D} |(\theta_i - \theta_j)|_{k,l} \\
&= \frac{1}{D} \|\text{vec}(\theta_i) - \text{vec}(\theta_j)\|_1 \geq \frac{rDs}{8D} = \frac{rs}{8}
\end{align*}$$

Subsequently, our parameters $\theta_i$ are $2\tau$-separated (in $\ell_{\infty}$ operator distance) with $\tau = rs/8$. As soon as the minimum in Equation (26) is reached by the third value, i.e. whenever

$$\frac{\gamma_{\ell}s}{\sqrt{Tpq_{\ell}}} \leq c \min\{\vartheta, \gamma_{\ell}\sqrt{1-\vartheta}\} \qquad (27)$$
We substitute the residual bounds from Lemma B.5:

$$
\begin{align*}
\mathbb{E}_{\Pi} [ \mathbf{1}_{E^c} \text{ KL} \{ \mathbb{P}_{\theta}(Y|\Pi) \| \mathbb{P}_0(Y|\Pi) \} ] &\le \frac{p \times \frac{T\sigma^4}{(1-\vartheta)^2} \|\theta\|_2^2 \|\theta\|_F^2 + p^2 \times \frac{2T\sigma^4}{(1-\vartheta)^3} \|\theta\|_F^2}{(\sigma^2 + \omega^2)^2} \\
&\le \left( \frac{\sigma^2}{\sigma^2 + \omega^2} \right)^2 \frac{2Tp(\|\theta\|_2^2 + p) \|\theta\|_F^2}{(1-\vartheta)^3} \\
&= \frac{2Tp(\|\theta\|_2^2 + p) \|\theta\|_F^2}{\gamma\ell}.
\end{align*}
$$

By Equation (23), this is equivalent to bounding the expected KL divergence regardless of the event E, hence the result. Note that our assumption on θ, combined with Lemma B.5, implies

$$
\|R(\theta)\|_2 \le \frac{2\sigma^2}{(1-\vartheta)^2} \|\theta\|_2 \le \frac{2\sigma^2}{(1-\vartheta)^2} \frac{(1-\vartheta)^2(\sigma^2 + \omega^2)}{4\sigma^2} \le \frac{\sigma^2 + \omega^2}{2} \quad \square
$$

B.9. Application of Fano’s method

Given the KL bound we just obtained, we are finally able to prove Theorem 3.2.

Proof. Fano’s method requires finding $M+1$ parameters $\theta_i$ such that $\theta_0 = 0$ and $\|\theta_i - \theta_j\|_F \ge 2\tau$ for $i \ne j$ (with $\tau$ to be specified), while keeping control upon the average KL divergence between the probability distributions $\mathbb{P}_{\theta_i}$ and $\mathbb{P}_0$. Judging by Lemma B.6, one way to achieve this control on the KL divergence is to bound the $\|\theta_i\|_F$ uniformly in $i$ (in other words, to choose them all inside a ball of fixed radius). We will then have to see how many $2\tau$-separated matrices we can fit in such a ball.

Let us consider the set $\mathcal{H}(r)$ of all block-diagonal $D \times D$ matrices with coefficients in $\{0, r\}$ such that each block has size $s \times s$ (we assume $s$ divides $D$). In particular, these matrices are all row- and column-sparse, with no more than $s$ non-zero coefficients per row or column. In terms of dimensionality, we are dealing with the (scaled) matrix equivalent of a $D^s$-dimensional hypercube, hence the notation $\mathcal{H}(r)$. It has cardinality $2^{D^s}$ and for every $\theta \in \mathcal{H}$, we have the following norm bounds: $\|\theta\|_2 \le rs$ and $\|\theta\|_F \le r\sqrt{Ds}$. The spectral norm bound on $\theta$ is obtained as the maximum spectral norm of each block, which we in turn control using the Frobenius norm of each block.

Unfortunately, in this hypercube, not all pairs of vertices are well-separated. That is why we need the Gilbert-Varshamov bound of Lemma C.10: according to this result, there exists a pruned subset $\mathcal{K}(r) \subset \mathcal{H}(r)$ containing 0 and such that $|\mathcal{K}(r)| \ge |\mathcal{H}(r)|^{1/8} = 2^{Ds/8}$ and $\|\mathrm{vec}(\theta_i) - \mathrm{vec}(\theta_j)\|_1 \ge \frac{rDs}{8}$ for all pairs of distinct vertices $\theta_i$ and $\theta_j$ in $\mathcal{K}(r)$. We choose our set of parameters $\theta_0, \theta_1, \dots, \theta_M$ to be exactly this pruned subset $\mathcal{K}(r)$, in particular $M + 1 = |\mathcal{K}(r)|$.

The missing ingredient is an upper bound on the maximum average KL divergence between $\mathbb{P}_{\theta_i}$ and $\mathbb{P}_0$: we can obtain it using Lemma B.6. We only need to assume

$$
\|\theta_i\|_F \le r\sqrt{Ds} \le \min \left\{ \vartheta, \frac{(1-\vartheta)^2(\sigma^2 + \omega^2)}{4\sigma^2} \right\}
$$
we can simplify the expression of $\tau$:

$$ \tau = c \frac{\gamma \ell s}{\sqrt{T p q \ell}} $$

In this case, by Lemma 27, we can conclude:

$$ \inf_{\hat{\theta} \in \Theta_s} \sup_{\theta \in \Theta_s} \mathbb{P}_{\theta} \left[ \|\hat{\theta} - \theta\|_{\infty} \ge c \frac{\gamma \ell s}{\sqrt{T p q \ell}} \right] \ge \frac{\log(M+1) - \log 2}{\log M} - \alpha \ge \frac{1}{2}. $$

□

# C USEFUL LEMMAS

## C.1 LINEAR ALGEBRA

The following set of results will sometimes be used in matrix calculations without explicit justifications.

**Lemma 22 (Weyl's inequality).** Let A and B be two $n \times n$ symmetric matrices. Then for all $i$ we have:

$$ \lambda_i(A) + \lambda_n(B) \le \lambda_i(A + B) \le \lambda_i(A) + \lambda_1(B). $$

In particular,

$$ \lambda_{\min}(A) + \lambda_{\min}(B) \le \lambda_{\min}(A + B). $$

*Proof.* See Horn and Johnson [2012, Theorem 4.3.1].

□

**Lemma 23 (Ostrowski).** Let S and A be two $n \times n$ matrices with S symmetric. For all $i$, there is a real number $r_i \in [s_{\min}(A)^2, s_{\max}(A)^2]$ such that $\lambda_i(ASA') = r_i\lambda_i(S)$, where $s_{\min}$ (resp. $s_{\max}$) denotes the minimum (resp. maximum) singular value.

*Proof.* See Horn and Johnson [2012, Theorem 4.5.9 and Corollary 4.5.11]

□

**Lemma 24 (Singular values of the Kronecker product).** Let A and B be two matrices. Then

$$ \|A \otimes B\|_2 \le \|A\|_2 \|B\|_2. $$

*Proof.* See Horn and Johnson [1994, Theorem 4.2.15].

□

**Lemma 25.** For any two matrices A and B, we have:

$$ \|AB\|_F \le \min \{\|A\|_2 \|B\|_F, \|A\|_F \|B\|_2\} $$

*Proof.* The Loewner order on symmetric matrices satisfies the following properties:

$$ \forall (P, Q) \in S_n(\mathbb{R}), \forall R, \quad P \preceq Q \implies R'PR \preceq R'QR $$

$$ \forall (P, Q) \in S_n(\mathbb{R}), \quad P \preceq Q \implies \mathrm{Tr}(P) \le \mathrm{Tr}(Q). $$

The first inequality is true because if $x$ is a vector, $x'R'(Q-P)Rx = (Rx)'(Q-P)(Rx) \ge 0$ due to the Loewner positivity of $Q-P$. The second inequality can be directly deduced from the relation between the spectra of $P$ and $Q$.

Therefore, since $A'A$ is symmetric,

$$ B'A'AB \le \lambda_{\max}(A'A)B'B $$

which implies

$$ \|AB\|_F^2 = \mathrm{Tr}(B'A'AB) \le \lambda_{\max}(AA') \mathrm{Tr}(B'B) = \|A\|_2^2 \|B\|_F^2. $$

The proof for the other inequality is identical.

□
to get the upper bound

$$ \begin{aligned} \max_i \mathbb{E}_{\Pi} \left[ \mathrm{KL} \left\{ \mathbb{P}_{\theta_i}(Y|\Pi) \| \mathbb{P}_{\theta_0}(Y|\Pi) \right\} \right] &\le \max_i \mathrm{KL}_{\mathrm{avg}} (\|\theta_i\|_2, \|\theta_i\|_F) \\ &\le \mathrm{KL}_{\mathrm{avg}}(rs, r\sqrt{Ds}). \end{aligned} $$

Since we must satisfy the constraint from Equation (27) in Fano's method, we will choose $r$ so that:

$$ \mathrm{KL}_{\mathrm{avg}}(rs, r\sqrt{Ds}) \le \alpha \log(M) = \alpha \log\left(2^{Ds/8} - 1\right) $$

with $\alpha = \frac{\log 3 - \log 2}{2 \log 2}$. We want to solve the previous inequality for $r$, and for that we start by replacing $\mathrm{KL}_{\mathrm{avg}}(rs, r\sqrt{Ds})$ with its value from Lemma B.6:

$$ \begin{aligned} \mathrm{KL}_{\mathrm{avg}}(rs, r\sqrt{Ds}) \le \alpha \log \left(2^{Ds/8} - 1\right) &\iff \frac{2}{\gamma_{\ell}} Tp \left((rs)^2 + p\right) (r\sqrt{Ds})^2 \le cDs \\ &\iff Ds^3 r^4 + pDs r^2 - c \frac{\gamma_{\ell}^2 Ds}{Tp} \le 0. \end{aligned} $$

If we consider this as a degree two polynomial in the variable $r^2$, its determinant is $\Delta = p^2 D^2 s^2 + 4Ds^3 c \frac{\gamma_{\ell}^2 Ds}{Tp}$. For $\beta$ to be small enough, $r^2$ must remain below the only positive root of the polynomial, namely

$$ r^2 \le \frac{-pDs + \sqrt{p^2 D^2 s^2 + c \frac{\gamma_{\ell}^2 D^2 s^4}{Tp}}}{2Ds^3} = \frac{p}{2s^2} \left( \sqrt{1 + c \frac{\gamma_{\ell}^2 s^2}{Tp^3}} - 1 \right). $$

If we assume the quantity $c \frac{\gamma_{\ell}^2 s^2}{Tp^3}$ inside the square root is smaller than 1, i.e.

$$ \frac{\gamma_{\ell} s}{\sqrt{Tp^3}} \le c, \qquad (24) $$

then we can lower-bound $\sqrt{1+x} - 1$ by its chord $(\sqrt{2} - 1)x$. In other words, a sufficient condition for $r^2$ to remain small enough is given by

$$ r^2 \le \frac{p}{2s^2} \times (\sqrt{2} - 1) c \frac{\gamma_{\ell}^2 s^2}{Tp^3} = c \frac{\gamma_{\ell}^2}{Tp^2}. $$

To sum up, we have three constraints on $r$:

$$ rs \le \vartheta \qquad rs \le \frac{(1-\vartheta)^2(\sigma^2 + \omega^2)}{4\sigma^2} = \frac{\sqrt{1-\vartheta}}{4}\gamma_{\ell} \qquad r \le \sqrt{c \frac{\gamma_{\ell}^2}{Tp^2}}. $$

We can therefore choose $r$ as the largest value satisfying all three of them:

$$ r = \frac{1}{s} \min \left\{ \vartheta, \frac{\gamma_{\ell} \sqrt{1-\vartheta}}{4}, c \frac{\gamma_{\ell} s}{p \sqrt{T}} \right\} \qquad (25) $$
**Lemma 26.** Let A and B be two matrices with compatible sizes: then

$$ \|AB\|_{\max} \leq \min\{\|A\|_{\infty}\|B\|_{\max}, \|A\|_{\max}\|B\|_{1}\}. $$

*Proof.*

$$ \|AB\|_{\max} = \max_{i,j} |(AB)_{i,j}| = \max_{i,j} \left| \sum_k A_{i,k} B_{k,j} \right| $$

We easily deduce:

$$ \|AB\|_{\max} \leq \max_{i} \left| \sum_{k} A_{i,k} \right| \times \|B\|_{\max} = \|A\|_{\infty} \|B\|_{\max} $$

$$ \|AB\|_{\max} \leq \|A\|_{\max} \times \max_{j} \left| \sum_{k} B_{k,j} \right| = \|A\|_{\max} \|B\|_{1} $$

□

## C.2 PROBABILITY

**Lemma 27 (Fano's method).** Let $\theta_0, \dots, \theta_M$ be $M+1$ parameters that are $2\tau$-separated w.r.t. a distance $d$

$$ \forall i \neq j, \quad d(\theta_i, \theta_j) \geq 2\tau $$

and such that the average KL divergence between $P_{\theta_i}$ and $P_{\theta_0}$ is small enough

$$ \frac{1}{M+1} \sum_{i=1}^{M} \mathrm{KL} \{ P_{\theta_i} \| P_{\theta_0} \} \leq \alpha \log M \quad \text{with} \quad 0 < \alpha < 1 \qquad (28) $$

Then the minimax probability of an error at threshold $\tau$ satisfies:

$$ \inf_{\hat{\theta}} \sup_{\theta \in \Theta_s} P_{\theta} \left[ d(\hat{\theta}, \theta) \geq \tau \right] \geq \frac{\log(M+1) - \log 2}{\log M} - \alpha. $$

*Proof.* See Tsybakov [2008, Section 2.2 + Corollary 2.6]. In particular, since $M \mapsto \frac{\log(M+1)-\log 2}{\log M}$ is increasing, setting $\alpha = \frac{\log(3)-\log(2)}{2\log(2)} \geq 1/2$ is enough to obtain a minimax risk greater than $\alpha$, as soon as $M \geq 3$. □

**Lemma 28 (Chain rule for KL divergence).** If $P_0$ and $P_1$ are probability densities on a product space $\mathcal{X} \times \mathcal{Y}$ with $\mathcal{X}$ discrete, then:

$$ \mathrm{KL} \{ P_0[X, Y] \| P_1[X, Y] \} = \mathrm{KL} \{ P_0[X] \| P_1[X] \} + \mathrm{E}_X [\mathrm{KL} \{ P_0[Y|X] \| P_1[Y|X] \}]. $$

*Proof.* See Cover and Thomas [2012, Theorem 2.5.3]. □

**Lemma 29 (KL divergence between Gaussians).** The KL divergence between two multivariate Gaussian distributions $P_0 = \mathcal{N}(\mu_0, \Sigma_0)$ and $P_1 = \mathcal{N}(\mu_1, \Sigma_1)$ of dimension $n$ is

$$ \mathrm{KL} \{ P_0 \| P_1 \} = \frac{1}{2} (\mathrm{Tr}(\Sigma_0 \Sigma_1^{-1}) + (\mu_1 - \mu_0)' \Sigma_1^{-1} (\mu_1 - \mu_0) - n + \mathrm{logdet}(\Sigma_1 \Sigma_0^{-1})) $$

*Proof.* See Duchi [2007, page 13]. □
To reach our conclusion, we simply need to remark that the vectorized $\ell_1$ distance between any two matrices in $K(r)$ gives us a lower bound on the operator $\ell_\infty$ distance that separates them:

$$ \begin{aligned} \|\theta_i - \theta_j\|_{\infty} &= \max_{k \in [D]} \sum_{l \in [D]} |(\theta_i - \theta_j)|_{k,l} \ge \frac{1}{D} \sum_{1 \le k,l \le D} |(\theta_i - \theta_j)|_{k,l} \\ &= \frac{1}{D} \|\mathrm{vec}(\theta_i) - \mathrm{vec}(\theta_j)\|_1 \ge \frac{rD_s}{8D} = \frac{rs}{8} \end{aligned} $$

Subsequently, our parameters $\theta_i$ are $2\tau$-separated (in $\ell_\infty$ operator distance) with $\tau = rs/8$. As soon as the minimum in Equation (25) is reached by the third value, i.e. whenever

$$ \frac{\gamma \ell_s}{p \sqrt{T}} \le c \min\{\vartheta, \gamma_\ell \sqrt{1 - \vartheta}\} \quad (26) $$

we can simplify the expression of $\tau$ as $\tau = c \frac{\gamma \ell_s}{p \sqrt{T}}$. In this case, by Lemma C.5, we can conclude:

$$ \inf_{\widehat{\theta} \in \Theta_s} \sup_{\theta \in \Theta_s} \mathbb{P}_{\theta} \left[ \|\widehat{\theta} - \theta\|_{\infty} \ge c \frac{\gamma \ell_s}{p \sqrt{T}} \right] \ge \frac{\log(M+1) - \log 2}{\log M} - \alpha \ge \frac{1}{2}. \quad \square $$

# Appendix C: Useful lemmas

## C.1. Linear algebra

The following set of results will sometimes be used in matrix calculations without explicit justifications.

**Lemma C.1 (Ostrowski).** Let $S$ and $A$ be two $n \times n$ matrices with $S$ symmetric. For all $i$, there is a real number $r_i \in [s_{\min}(A)^2, s_{\max}(A)^2]$ such that $\lambda_i(ASA') = r_i\lambda_i(S)$, where $s_{\min}(\text{resp. } s_{\max})$ denotes the minimum (resp. maximum) singular value, while $\lambda_i$ denotes the $i$-th eigenvalue.

*Proof.* See Horn and Johnson [19, Theorem 4.5.9 and Corollary 4.5.11] □

**Lemma C.2 (Singular values of the Kronecker product).** Let $A$ and $B$ be two matrices. Then $\|A \otimes B\|_2 \le \|A\|_2 \|B\|_2$.

*Proof.* See Horn and Johnson [18, Theorem 4.2.15]. □

**Lemma C.3.** For any two matrices $A$ and $B$, we have:

$$ \|AB\|_F \le \min \{\|A\|_2 \|B\|_F, \|A\|_F \|B\|_2\} $$

*Proof.* The Loewner order $\le$ on symmetric matrices satisfies the following properties:

$$ \begin{aligned} \forall (P, Q) \in S_n(\mathbb{R}), \forall R, P \le Q &\implies R'PR \le R'QR \\ \forall (P, Q) \in S_n(\mathbb{R}), P \le Q &\implies \mathrm{Tr}(P) \le \mathrm{Tr}(Q). \end{aligned} $$

The first inequality is true because if $x$ is a vector, $x'R'(Q-P)Rx = (Rx)'(Q-P)(Rx) \ge 0$ due to the Loewner positivity of $Q-P$. The second inequality can be directly deduced from
**Lemma 30** (KL divergence between close Gaussians). Let $\Delta$ be a symmetric matrix of size $n$ such that $\lambda_{\min}(\Delta) > -1$, and let $M$ be a rectangular matrix such that $MM' > 0$. Then the KL divergence between

$$ \mathbb{P}_1 = \mathcal{N}(\mu, M(I + \Delta)M') \quad \text{and} \quad \mathbb{P}_0 = \mathcal{N}(\mu, MM') $$

satisfies

$$ \mathrm{KL} \{ \mathbb{P}_1 \| \mathbb{P}_0 \} \leq \frac{\|\Delta\|_F^2}{2(1 + \lambda_{\min}(\Delta))}. $$

*Proof.* From Lemma 29 (beware of the switch between $\mathbb{P}_0$ and $\mathbb{P}_1$) we get:

$$ \begin{aligned} \mathrm{KL} \{ \mathbb{P}_1 \| \mathbb{P}_0 \} &= \frac{1}{2} (\mathrm{Tr}(\Sigma_1 \Sigma_0^{-1}) + (\mu_0 - \mu_1)' \Sigma_0^{-1} (\mu_0 - \mu_1) - n + \mathrm{logdet}(\Sigma_0 \Sigma_1^{-1})) \\ &= \frac{1}{2} (\mathrm{Tr}(M(I + \Delta)M^{-1}) - n - \mathrm{logdet}(M(I + \Delta)M^{-1})) \\ &= \frac{1}{2} (\mathrm{Tr}(\Delta) - \mathrm{logdet}(I + \Delta)). \end{aligned} $$

As it happens, for small deviations from the identity, the log-determinant is almost equal to the trace. Indeed, since

$$ \forall x > -1, \quad \log(1 + x) \geq \frac{x}{1 + x}, $$

we have

$$ \begin{aligned} \mathrm{Tr}(\Delta) - \mathrm{logdet}(I + \Delta) &= \sum_{k=1}^{n} \lambda_k(\Delta) - \sum_{k=1}^{n} \log(1 + \lambda_k(\Delta)) \\ &\leq \sum_{k=1}^{n} \lambda_k(\Delta) - \sum_{k=1}^{n} \frac{\lambda_k(\Delta)}{1 + \lambda_k(\Delta)} \\ &= \sum_{k=1}^{n} \frac{\lambda_k(\Delta)^2}{1 + \lambda_k(\Delta)} \leq \frac{1}{\min_k(1 + \lambda_k(\Delta))} \sum_{k=1}^{n} \lambda_k(\Delta)^2 \\ &= \frac{\|\Delta\|_F^2}{1 + \lambda_{\min}(\Delta)}. \end{aligned} $$

□

**Lemma 31** (Chernoff inequality for Bernoulli variables). Let $(X_t)$ be sequence of independent $\mathcal{B}(p)$ variables. Their average satisfies

$$ \forall u \in [0, 1], \quad \mathbb{P} \left( \left| \frac{1}{T} \sum_{t=1}^{T} X_t - p \right| \geq up \right) \leq c_1 \exp(-c_2 u^2 T p). $$

*Proof.* See Dubhashi and Panconesi [2009, Theorem 1.1].

□

**Lemma 32** (Doeblin condition and mixing time). Let $(X_t)$ be an irreducible aperiodic Markov chain with state space $\mathcal{X}$, transition matrix $P$ and stationary distribution $\mu$. Suppose that $(X_t)$ satisfies the Doeblin condition:

$$ \exists r \in \mathbb{N}, \exists \delta > 0, \forall (x, y) \in \mathcal{X}^2, P^r(x, y) \geq \delta \mu(y). $$

Then the mixing time of $X_t$, defined as

$$ t_{\mathrm{mix}}(\epsilon) = \min \left\{ t \in \mathbb{N} : \max_{x \in \mathcal{X}} \| P^t(x, \cdot) - \mu \|_{\mathrm{TV}} \leq \epsilon \right\}, $$

satisfies:

$$ t_{\mathrm{mix}}(\epsilon) \geq r \left( 1 + \frac{\log \frac{1}{\epsilon}}{\log \frac{1}{1-\delta}} \right). $$
the relation between the spectra of P and Q. Therefore, since A'A is symmetric, B'A'AB ≤ λmax(A'A)B'B, which implies

$$ ||AB||_F^2 = \mathrm{Tr}(B'A'AB) \le \lambda_{\max}(AA') \mathrm{Tr}(B'B) = ||A||_2^2 ||B||_F^2. $$

The proof for the other inequality is identical. □

**Lemma C.4.** Let A and B be two matrices with compatible sizes: then

$$ ||AB||_{\max} \le \min\{||A||_{\infty}||B||_{\max}, ||A||_{\max}||B||_1\}. $$

*Proof.*

$$ ||AB||_{\max} = \max_{i,j} |(AB)_{i,j}| = \max_{i,j} \left| \sum_k A_{i,k} B_{k,j} \right| $$

We easily deduce:

$$ ||AB||_{\max} \le \max_i \left| \sum_k A_{i,k} \right| \times ||B||_{\max} = ||A||_{\infty} ||B||_{\max} $$

$$ ||AB||_{\max} \le ||A||_{\max} \times \max_j \left| \sum_k B_{k,j} \right| = ||A||_{\max} ||B||_1 $$

□

## C.2. Probability

**Lemma C.5 (Fano's method).** Let $\theta_0, \dots, \theta_M$ be $M+1$ parameters that are $2\tau$-separated w.r.t. a distance $d$ ($\forall i \ne j$, $d(\theta_i, \theta_j) \ge 2\tau$) and such that the average KL divergence between $P_{\theta_i}$ and $P_{\theta_0}$ is small enough

$$ \frac{1}{M+1} \sum_{i=1}^{M} \mathrm{KL} \{ \mathbb{P}_{\theta_i} || \mathbb{P}_{\theta_0} \} \le \alpha \log M \quad \text{with} \quad 0 < \alpha < 1 \quad (27) $$

Then the minimax probability of an error at threshold $\tau$ satisfies:

$$ \inf_{\hat{\theta} \in \Theta_s} \sup_{\theta \in \Theta_s} \mathbb{P}_{\theta} \left[ d(\hat{\theta}, \theta) \ge \tau \right] \ge \frac{\log(M+1) - \log 2}{\log M} - \alpha. $$

*Proof.* See Tsybakov [37, Section 2.2 + Corollary 2.6]. In particular, since $M \mapsto \frac{\log(M+1)-\log 2}{\log M}$ is increasing, setting $\alpha = \frac{\log(3)-\log(2)}{2\log(2)} \ge 1/2$ is enough to obtain a minimax risk greater than $\alpha$, as soon as $M \ge 3$. □

**Lemma C.6 (Chain rule for KL divergence).** If $P_0$ and $P_1$ are probability densities on a product space $X \times Y$ with $X$ discrete, then:

$$ \mathrm{KL} \{ \mathbb{P}_0[X, Y] || \mathbb{P}_1[X, Y] \} = \mathrm{KL} \{ \mathbb{P}_0[X] || \mathbb{P}_1[X] \} + \mathrm{E}_X [ \mathrm{KL} \{ \mathbb{P}_0[Y|X] || \mathbb{P}_1[Y|X] \} ] $$

*Proof.* See Cover and Thomas [7, Theorem 2.5.3]. □

**Lemma C.7 (KL divergence between Gaussians).** The KL divergence between two multivariate Gaussian distributions $P_0 = N(\mu_0, \Sigma_0)$ and $P_1 = N(\mu_1, \Sigma_1)$ of dimension $n$ is

$$ \mathrm{KL} \{ \mathbb{P}_0 || \mathbb{P}_1 \} = \frac{1}{2} \left( \mathrm{Tr}(\Sigma_0 \Sigma_1^{-1}) + (\mu_1 - \mu_0)' \Sigma_1^{-1} (\mu_1 - \mu_0) - n + \mathrm{logdet}(\Sigma_1 \Sigma_0^{-1}) \right). $$
*Proof.* The proof of Levin and Peres [2017, Theorem 5.4] shows that with our assumptions,

$$ \forall x \in \mathcal{X}, \quad \|P^t(x, \cdot) - \mu\|_{\text{TV}} \le (1 - \delta)^{\lfloor t/r \rfloor}. $$

From which we can deduce a sufficient condition for $\epsilon$-mixing:

$$ (1 - \delta)^{\lfloor t/r \rfloor} \le \epsilon \iff \left\lfloor \frac{t}{r} \right\rfloor \ge \frac{\log(\epsilon)}{\log(1 - \delta)} \iff \frac{t}{r} - 1 \ge \frac{\log \frac{1}{\epsilon}}{\log \frac{1}{1 - \delta}}. $$

The result follows easily.

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

**Lemma 33** (Chernoff inequality for Markov chains). Let $(X_t)$ be an ergodic stationary Markov chain with finite state space $\mathcal{X}$. We consider a function $f: \mathcal{X} \to \mathbb{R}$ such that $\mathbb{E}[f(X_t)] = \mu$. Then

$$ \forall u \in [0, 1], \quad \mathbb{P}\left(\left|\frac{1}{T}\sum_{t=1}^{T} X_t - \mu\right| \ge u\mu\right) \le c_1 \exp\left(-c_2 \frac{u^2 T \mu}{t_{\text{mix}}(1/8)}\right) $$

*Proof.* See Chung et al. [2012, Theorem 3]

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

**Lemma 34** (Chernoff inequality for Markov chains under Doeblin condition). Under the hypotheses of the previous two Lemmas (32 and 33), if the parameters $r$ and $\delta$ in the Doeblin condition are constants, then we have:

$$ \forall u \in [0, 1], \quad \mathbb{P}\left(\left|\frac{1}{T}\sum_{t=1}^{T} X_t - \mu\right| \ge u\mu\right) \le c_1 \exp\left(-c_2 u^2 T \mu\right) $$

*Proof.* By Lemma 32, since $r$ and $\delta$ are constants, the $\frac{1}{8}$-mixing time of $(X_t)$ can be bounded by a constant

$$ t_{\text{mix}}(1/8) \le r \left( 1 + \frac{\log(8)}{\log \frac{1}{1-\delta}} \right) \le c_3, $$

which we merge with the $c_2$ inside the exponential of Lemma 33.

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

**Lemma 35** (Gilbert-Varshamov). Let $\mathcal{H} = \{0, 1\}^d$ be the $d$-dimensional binary hypercube. If $d \ge 8$, there exists a pruned subset $\mathcal{K} \subset \mathcal{H}$ such that

$$ \forall (x, y) \in \mathcal{K}, \quad \|x - y\|_1 \ge \frac{d}{8} \quad \text{and} \quad |\mathcal{K}| \ge 2^{d/8}. $$

*Proof.* See Tsybakov [2008, Lemma 2.9]

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

**Lemma 36** (Hanson-Wright inequality: Gaussian case). Let $A$ be a square matrix. If $X$ and $Y$ are two independent standard Gaussian vectors, we have:

$$ \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) \le 2 \exp \left( -c \min \left\{ \frac{u^2}{\|A\|_F^2}, \frac{u}{\|A\|_2} \right\} \right) $$

$$ \mathbb{P}(|X'AY - \mathbb{E}[X'AY]| \ge u) \le 2 \exp \left( -c \min \left\{ \frac{u^2}{\|A\|_F^2}, \frac{u}{\|A\|_2} \right\} \right). $$

*Proof.* See Vershynin [2018, Theorem 6.2.1] for the first inequality. We will see that it implies the second one. Let us define

$$ \tilde{A} = \begin{bmatrix} 0 & A \\ 0 & 0 \end{bmatrix} \quad \text{and} \quad \tilde{X} = \begin{bmatrix} X \\ Y \end{bmatrix}. $$

We note that $\|\tilde{A}\|_F = \|A\|_F$ and $\|\tilde{A}\|_2 = \|A\|_2$. Applying the first inequality to $\tilde{X}'\tilde{A}\tilde{X} = X'AY$ yields the expected result.

<figure><img src="image_18.png" /></figure>
Proof. See Duchi [14, page 13].

□

**Lemma C.8 (KL divergence between close Gaussians).** Let $\Delta$ be a symmetric matrix of size $n$ such that $\lambda_{\min}(\Delta) > -1$, and let $M$ be a rectangular matrix such that $MM' > 0$. Then the KL divergence between $\mathbb{P}_1 = N(\mu, M(I+\Delta)M')$ and $\mathbb{P}_0 = N(\mu, MM')$ satisfies

$$ \text{KL} \{\mathbb{P}_1 \| \mathbb{P}_0\} \le \frac{\|\Delta\|_F^2}{2(1 + \lambda_{\min}(\Delta))}. $$

*Proof.* From Lemma C.7 (beware of the switch between $\mathbb{P}_0$ and $\mathbb{P}_1$) we get:

$$ \begin{aligned} \text{KL} \{\mathbb{P}_1 \| \mathbb{P}_0\} &= \frac{1}{2} \left( \text{Tr}(\Sigma_1 \Sigma_0^{-1}) + (\mu_0 - \mu_1)' \Sigma_0^{-1} (\mu_0 - \mu_1) - n + \text{logdet}(\Sigma_0 \Sigma_1^{-1}) \right) \\ &= \frac{1}{2} \left( \text{Tr}(M(I + \Delta)M^{-1}) - n - \text{logdet}(M(I + \Delta)M^{-1}) \right) \\ &= \frac{1}{2} (\text{Tr}(\Delta) - \text{logdet}(I + \Delta)). \end{aligned} $$

As it happens, for small deviations from the identity, the log-determinant is almost equal to the trace. Indeed, since for all $x > -1$, it holds that $\log(1+x) \ge \frac{x}{1+x}$, we have

$$ \begin{aligned} \text{Tr}(\Delta) - \text{logdet}(I + \Delta) &= \sum_{k=1}^{n} \lambda_k(\Delta) - \sum_{k=1}^{n} \log(1 + \lambda_k(\Delta)) \\ &\le \sum_{k=1}^{n} \lambda_k(\Delta) - \sum_{k=1}^{n} \frac{\lambda_k(\Delta)}{1 + \lambda_k(\Delta)} \\ &= \sum_{k=1}^{n} \frac{\lambda_k(\Delta)^2}{1 + \lambda_k(\Delta)} \le \frac{1}{\min_k(1 + \lambda_k(\Delta))} \sum_{k=1}^{n} \lambda_k(\Delta)^2 \\ &= \frac{\|\Delta\|_F^2}{1 + \lambda_{\min}(\Delta)}. \end{aligned} \quad \square $$

**Lemma C.9 (Chernoff inequality for Bernoulli variables).** Let $(X_t)$ be a sequence of independent $\mathcal{B}(p)$ variables. Their average satisfies

$$ \forall u \in [0, 1], \quad \mathbb{P} \left( \left| \frac{1}{T} \sum_{t=1}^{T} X_t - p \right| \ge up \right) \le c_1 \exp \left( -c_2 u^2 T p \right). $$

*Proof.* See Dubhashi and Panconesi [13, Theorem 1.1].

□

**Lemma C.10 (Gilbert-Varshamov).** Let $\mathcal{H} = \{0,1\}^d$ be the $d$-dimensional binary hypercube. If $d \ge 8$, there exists a pruned subset $\mathcal{K} \subset \mathcal{H}$ such that $\forall (x,y) \in \mathcal{K}$, $\|x-y\|_1 \ge \frac{d}{8}$ and $|\mathcal{K}| \ge 2^{d/8}$.

*Proof.* See Tsybakov [37, Lemma 2.9]

□

**Lemma C.11 (Hanson-Wright inequality: Gaussian case).** Let $A$ be a square matrix. If $X$ and $Y$ are two independent standard Gaussian vectors, we have:

$$ \begin{aligned} \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) &\le 2 \exp \left( -c \min \left\{ \frac{u^2}{\|A\|_F^2}, \frac{u}{\|A\|_2} \right\} \right) \\ \mathbb{P}(|X'AY - \mathbb{E}[X'AY]| \ge u) &\le 2 \exp \left( -c \min \left\{ \frac{u^2}{\|A\|_F^2}, \frac{u}{\|A\|_2} \right\} \right). \end{aligned} $$
**Lemma 37 (Conditional Hanson-Wright inequality).** Let A be a random square matrix such that with probability 1-δ,

$$ \|A\|_2 \le M_2 \quad \text{and} \quad \|A\|_F^2 \le M_F^2. $$

If X and Y are two independent standard Gaussian vectors independent of A, we have:

$$ \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) \le \delta + 2 \exp \left( -c \min \left\{ \frac{u^2}{M_F^2}, \frac{u}{M_2} \right\} \right) + \mathbb{P}(|\mathrm{Tr}(A - \mathbb{E}[A])| \ge u/2) $$

$$ \mathbb{P}(|X'AY - \mathbb{E}[X'AY]| \ge u) \le \delta + 2 \exp \left( -c \min \left\{ \frac{u^2}{M_F^2}, \frac{u}{M_2} \right\} \right). $$

*Proof.* We start with the first case. Since A is a discrete random matrix with a finite set A of possible values,

$$ \begin{aligned} \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) &= \sum_{a \in A} \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u \cap A = a) \\ &= \sum_{a \in A} \mathbb{P}(|X'aX - \mathbb{E}[X'AX]| \ge u \cap A = a). \end{aligned} $$

Using independence between X and A gives us

$$ \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) = \sum_{a \in A} \mathbb{P}(|X'aX - \mathbb{E}[X'AX]| \ge u) \mathbb{P}(A = a). $$

We now split the set of feasible values A into

$$ A_{\le} = \{a \in A : \|a\|_F^2 \le M_F^2\} \quad \text{and} \quad A_{>} = \{a \in A : \|a\|_F^2 > M_F^2\}. $$

Since we assumed $\mathbb{P}(A \in A_{>}) = \sum_{a \in A_{>}} \mathbb{P}(A=a) \le \delta$, we get:

$$ \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) \le \delta + \sum_{a \in A_{\le}} \mathbb{P}(|X'aX - \mathbb{E}[X'AX]| \ge u) \mathbb{P}(A=a). $$

Unfortunately, Lemma 36 only lets us bound

$$ \mathbb{P}(|X'aX - \mathbb{E}[X'aX]| \ge u) \quad \text{and not} \quad \mathbb{P}(|X'aX - \mathbb{E}[X'AX]| \ge u) $$

(notice the change inside the expectation), which means we need an additional step. For a fixed $a \in A_{\le}$, we use independence and normality to obtain

$$ \begin{aligned} \mathbb{E}[X'aX] - \mathbb{E}[X'AX] &= \mathbb{E}[\mathrm{Tr}(X'(a-A)X)] = \mathrm{Tr}(\mathbb{E}[XX'(a-A)]) \\ &= \mathrm{Tr}(\mathbb{E}[XX']\mathbb{E}[a-A]) = \mathrm{Tr}(a - \mathbb{E}[A]). \end{aligned} $$

We are now ready to decompose, with the help of the union bound:

$$ \begin{aligned} \mathbb{P}(|X'aX - \mathbb{E}[X'AX]| \ge u) &= \mathbb{P}(|X'aX - \mathbb{E}[X'aX] + \mathbb{E}[X'aX] - \mathbb{E}[X'AX]| \ge u) \\ &\le \mathbb{P}(|X'aX - \mathbb{E}[X'aX]| \ge u/2) + \mathbb{P}(|\mathbb{E}[X'aX] - \mathbb{E}[X'AX]| \ge u/2) \\ &\le 2 \exp \left( -c \min \left\{ \frac{u^2}{\|a\|_F^2}, \frac{u}{\|a\|_2} \right\} \right) + \mathbf{1} \{|\mathrm{Tr}(a - \mathbb{E}[A])| \ge u/2\}. \end{aligned} $$

This implies:

$$ \begin{aligned} \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) &\le \delta + \sum_{a \in A_{\le}} \mathbb{P}(A=a) \mathbb{P}(|X'aX - \mathbb{E}[X'AX]| \ge u) \\ &\le \delta + \sum_{a \in A_{\le}} \mathbb{P}(A=a) \times 2 \exp \left[ -c \min \left\{ \frac{u^2}{\|a\|_F^2}, \frac{u}{\|a\|_2} \right\} \right] \\ &\quad + \sum_{a \in A_{\le}} \mathbb{P}(A=a) \times \mathbf{1}\{|\mathrm{Tr}(a - \mathbb{E}[A])| \ge u/2\}. \end{aligned} $$
**Proof.** See Vershynin [38, Theorem 6.2.1] for the first inequality. We will see that it implies the second one. Let us define $\tilde{A} = \begin{bmatrix} 0 & A \\ 0 & 0 \end{bmatrix}$ and $\tilde{X} = \begin{bmatrix} X \\ Y \end{bmatrix}$. We note that $\|\tilde{A}\|_F = \|A\|_F$ and $\|\tilde{A}\|_2 = \|A\|_2$. Applying the first inequality to $\tilde{X}'\tilde{A}\tilde{X} = X'AY$ yields the expected result. $\square$

**Lemma C.12 (Conditional Hanson-Wright inequality).** Let A be a random square matrix such that with probability $1-\delta$, $\|A\|_2 \le M_2$ and $\|A\|_F^2 \le M_F^2$. If X and Y are two independent standard Gaussian vectors independent of A, we have:

$$ \begin{aligned} \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) &\le \delta + 2 \exp \left( -c \min \left\{ \frac{u^2}{M_F^2}, \frac{u}{M_2} \right\} \right) \\ &\quad + \mathbb{P}(|\mathrm{Tr}(A - \mathbb{E}[A])| \ge u/2) \\ \mathbb{P}(|X'AY - \mathbb{E}[X'AY]| \ge u) &\le \delta + 2 \exp \left( -c \min \left\{ \frac{u^2}{M_F^2}, \frac{u}{M_2} \right\} \right). \end{aligned} $$

**Proof.** We start with the first case. Since A is a discrete random matrix with a finite set $\mathcal{A}$ of possible values,

$$ \begin{aligned} \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) &= \sum_{a \in \mathcal{A}} \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u \cap A = a) \\ &= \sum_{a \in \mathcal{A}} \mathbb{P}(|X'aX - \mathbb{E}[X'AX]| \ge u \cap A = a). \end{aligned} $$

Using independence between X and A gives us

$$ \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) = \sum_{a \in \mathcal{A}} \mathbb{P}(|X'aX - \mathbb{E}[X'AX]| \ge u) \mathbb{P}(A = a). $$

We now split the set of feasible values $\mathcal{A}$ into

$$ \mathcal{A}_{\le} = \{a \in \mathcal{A} : \|a\|_F^2 \le M_F^2\} \quad \text{and} \quad \mathcal{A}_{>} = \{a \in \mathcal{A} : \|a\|_F^2 > M_F^2\}. $$

Since we assumed $\mathbb{P}(A \in \mathcal{A}_{>}) = \sum_{a \in \mathcal{A}_{>}} \mathbb{P}(A = a) \le \delta$, we get:

$$ \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) \le \delta + \sum_{a \in \mathcal{A}_{\le}} \mathbb{P}(|X'aX - \mathbb{E}[X'AX]| \ge u) \mathbb{P}(A = a). $$

Unfortunately, Lemma C.11 only lets us bound

$$ \mathbb{P}(|X'aX - \mathbb{E}[X'aX]| \ge u) \quad \text{and not} \quad \mathbb{P}(|X'aX - \mathbb{E}[X'AX]| \ge u) $$

(notice the change inside the expectation), which means we need an additional step. For a fixed $a \in \mathcal{A}_{\le}$, we use independence and normality to obtain

$$ \begin{aligned} \mathbb{E}[X'aX] - \mathbb{E}[X'AX] &= \mathbb{E}[\mathrm{Tr}(X'(a-A)X)] = \mathrm{Tr}(\mathbb{E}[XX'(a-A)]) \\ &= \mathrm{Tr}(\mathbb{E}[XX']\mathbb{E}[a-A]) = \mathrm{Tr}(a - \mathbb{E}[A]). \end{aligned} $$

We are now ready to decompose, with the help of the union bound:

$$ \mathbb{P}(|X'aX - \mathbb{E}[X'AX]| \ge u) $$
By definition of $\mathcal{A}_{\le}$,

$$ \begin{aligned} \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) &\le \delta + \sum_{a \in \mathcal{A}_{\le}} \mathbb{P}(A=a) \times 2 \exp \left( -c \min \left\{ \frac{u^2}{M_F^2}, \frac{u}{M_2} \right\} \right) \\ &\quad + \mathbb{P}(|\mathrm{Tr}(A - \mathbb{E}[A])| \ge u/2) \\ &\le \delta + 2 \exp \left( -c \min \left\{ \frac{u^2}{M_F^2}, \frac{u}{M_2} \right\} \right) + \mathbb{P}(|\mathrm{Tr}(A - \mathbb{E}[A])| \ge u/2). \end{aligned} $$

The proof for $X'AY$ follows the same lines, except that we replace $\mathbb{E}[XX'] = I$ by $\mathbb{E}[XY'] = 0$, which removes the trace term in the final expression. □

**Lemma 38** (Heuristic optimality of the signal-to-noise ratio). In the one-dimensional setting with full observations, the dependency of the error in $1 + \frac{\sigma^2}{\omega^2}$ is “coherent” with the asymptotic behavior of the MLE.

*Proof.* Let us consider the case where $D = 1$ and $p = 1$, since we are mainly interested in the role of the parameters $\sigma^2$ and $\omega^2$. In this case, Theorem 2 argues that the error of any estimator should grow at least like $\gamma_{\ell} = 1 + \frac{\omega^2}{\sigma^2}$. We also note that in this simple scenario, Theorem 1 states that $\gamma_u \propto \gamma_{\ell}$.

We will compare this to the asymptotic error of the Maximum Likelihood Estimator (MLE) $\hat{\theta}$, which (for well-behaved models) is given by the inverse of the Fisher information matrix. To make this statement more precise, we will invoke Douc et al. [2014, Proposition 2.14]. Let us verify the conditions:

* The process is stable, i.e. $\rho(\theta) < 1$. We made sure of that by assuming $\|\theta\|_2 \le \vartheta < 1$.

* The sampling matrix $\Pi_t$ is constant across time. Although this assumption is not essential, it is true here since $p = 1$ and $D = 1$ hence $\Pi_t = I_1$.

* The model has the smallest possible dimension.

* The true parameter $\theta$ is identifiable and does not lie on the boundary of $\Theta_s$. Identifiability is easily deduced from Lemma 1 by observing that $\theta = \Gamma_1(\theta)\Gamma_0(\theta)^{-1}$ can be entirely deduced from distribution moments.

Since all of these prerequisites hold here, Douc et al. [2014, Proposition 2.14] gives us a Central Limit Theorem for the MLE of linear Gaussian models:

$$ \sqrt{T}(\hat{\theta} - \theta) \xrightarrow[T \to \infty]{\mathcal{L}} \mathcal{N}(0, \mathcal{I}_{\infty}(\theta)^{-1}) \quad \text{where} \quad \mathcal{I}_{\infty}(\theta) = \lim_{T \to \infty} \frac{\mathcal{I}_T(\theta)}{T}. $$

We only have to compute the Fisher information matrix $\mathcal{I}_T(\theta)$. The covariance matrix of $Y$ is given by Lemma 16, but in our case the sampling matrix is constant, and we obtain the simpler (unconditional) result

$$ \mathrm{Cov}_{\theta}[Y] = (\sigma^2 + \omega^2)I_T + R(\theta), $$

where the residual $R(\theta)$ is of order 1 in $\theta$. Indeed, our simplifying assumptions imply $\Gamma_0(\theta) = \frac{\sigma^2}{1-\theta^2}$ and therefore

$$ R(\theta) = \frac{\sigma^2}{1 - \theta^2} \begin{pmatrix} \theta^2 & \theta^1 & \theta^2 & \cdots \\ \theta^1 & \theta^2 & \theta^1 & \cdots \\ \theta^2 & \theta^1 & \theta^2 & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix} \quad \partial_{\theta} R(\theta) = \sigma^2 \begin{pmatrix} 0 & 1 & 0 & \cdots \\ 1 & 0 & 1 & \cdots \\ 0 & 1 & 0 & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix} + \mathcal{O}(\theta). $$

The Fisher information of $Y$ with respect to $\theta$ has an explicit formula [Malagò and Pistone, 2015, Section 3.5]:

$$ \begin{aligned} \mathcal{I}_T(\theta) &= \frac{1}{2} \mathrm{Tr} [\mathrm{Cov}_{\theta}[Y]^{-1} \partial_{\theta} \mathrm{Cov}_{\theta}[Y] \mathrm{Cov}_{\theta}[Y]^{-1} \partial_{\theta} \mathrm{Cov}_{\theta}[Y]] \\ &= \frac{1}{2} \mathrm{Tr} \left[ \left( I + \frac{R(\theta)}{\sigma^2 + \omega^2} \right)^{-1} \frac{\partial_{\theta} R(\theta)}{\sigma^2 + \omega^2} \left( I + \frac{R(\theta)}{\sigma^2 + \omega^2} \right)^{-1} \frac{\partial_{\theta} R(\theta)}{\sigma^2 + \omega^2} \right]. \end{aligned} $$
$$
\begin{align*}
&= \mathbb{P}(|X'aX - \mathbb{E}[X'aX]| + \mathbb{E}[X'aX] - \mathbb{E}[X'AX]| \ge u) \\
&\le \mathbb{P}(|X'aX - \mathbb{E}[X'aX]| \ge u/2) + \mathbb{P}(|\mathbb{E}[X'aX] - \mathbb{E}[X'AX]| \ge u/2) \\
&\le 2 \exp\left(-c \min\left\{\frac{u^2}{\|a\|_F^2}, \frac{u}{\|a\|_2}\right\}\right) + \mathbf{1}\{|\mathrm{Tr}(a - \mathbb{E}[A])| \ge u/2\}.
\end{align*}
$$

This implies:

$$
\begin{align*}
\mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) &\le \delta + \sum_{a \in \mathcal{A} \le} \mathbb{P}(A=a) \mathbb{P}(|X'aX - \mathbb{E}[X'AX]| \ge u) \\
&\le \delta + \sum_{a \in \mathcal{A} \le} \mathbb{P}(A=a) \times 2 \exp \left[ -c \min \left\{ \frac{u^2}{\|a\|_F^2}, \frac{u}{\|a\|_2} \right\} \right] \\
&\quad + \sum_{a \in \mathcal{A} \le} \mathbb{P}(A=a) \times \mathbf{1}\{|\mathrm{Tr}(a - \mathbb{E}[A])| \ge u/2\}.
\end{align*}
$$

By definition of $\mathcal{A}_\le$,

$$
\begin{align*}
& \mathbb{P}(|X'AX - \mathbb{E}[X'AX]| \ge u) \\
&\le \delta + \sum_{a \in \mathcal{A} \le} \mathbb{P}(A=a) \times 2 \exp \left( -c \min \left\{ \frac{u^2}{M_F^2}, \frac{u}{M_2} \right\} \right) + \mathbb{P} \left( |\mathrm{Tr}(A - \mathbb{E}[A])| \ge u/2 \right) \\
&\le \delta + 2 \exp \left( -c \min \left\{ \frac{u^2}{M_F^2}, \frac{u}{M_2} \right\} \right) + \mathbb{P} \left( |\mathrm{Tr}(A - \mathbb{E}[A])| \ge u/2 \right).
\end{align*}
$$

The proof for X'AY follows the same lines, except that we replace $\mathbb{E}[XX'] = I$ by $\mathbb{E}[XY'] = 0$, which removes the trace term in the final expression. $\square$

**Lemma C.13** (Heuristic optimality of the signal-to-noise ratio). In the one-dimensional setting with full observations, the dependency of the error in $1 + \frac{\omega^2}{\sigma^2}$ is “coherent” with the asymptotic behavior of the MLE.

*Proof.* Let us consider the case where $D = 1$ and $p = 1$, since we are mainly interested in the role of the parameters $\sigma^2$ and $\omega^2$. In this case, Theorem 3.2 argues that the error of any estimator should grow at least like $\gamma_\ell = 1 + \frac{\omega^2}{\sigma^2}$. We also note that in this simple scenario, Theorem 3.1 states that $\gamma_u \propto \gamma_\ell$.

We will compare this to the asymptotic error of the Maximum Likelihood Estimator (MLE) $\hat{\theta}$, which (for well-behaved models) is given by the inverse of the Fisher information matrix. To make this statement more precise, we will invoke Douc, Moulines and Stoffer [11, Proposition 2.14]. Let us verify the conditions:

* The process is stable, i.e. $\rho(\theta) < 1$. We made sure of that by assuming $\|\theta\|_2 \le \vartheta < 1$.

* The sampling matrix $\Pi_t$ is constant across time. Although this assumption is not essential, it is true here since $p = 1$ and $D = 1$ hence $\Pi_t = I_1$.

* The model has the smallest possible dimension.

* The true parameter $\theta$ is identifiable and does not lie on the boundary of $\Theta_s$. Identifiability is easily deduced from Lemma A.1 by observing that $\theta = \Gamma_1(\theta)\Gamma_0(\theta)^{-1}$ can be entirely deduced from distribution moments.
If assume $\theta$ is small and perform a Taylor expansion, we get:

$$ \mathcal{I}_T(\theta) \approx \frac{1}{2(\sigma^2 + \omega^2)^2} \mathrm{Tr}[(\partial_\theta R(\theta))^2]. $$

Incidentally, we also note that at the lowest order in $\theta$,

$$ \mathrm{Tr}[(\partial_{\theta} R(\theta))^2] = \|\partial_{\theta} R(\theta)\|_{F}^{2} \approx 2\sigma^{4}(T - 1). $$

Which gives us an approximate information matrix for $T$ steps:

$$ \mathcal{I}_T(\theta) \approx \frac{\mathrm{Tr}[(\partial_{\theta} R(\theta))^2]}{2(\sigma^2 + \omega^2)^2} \approx \frac{T}{2} \left( \frac{\sigma^2}{\sigma^2 + \omega^2} \right)^2. $$

Taking the temporal limit yields:

$$ \mathcal{I}_{\infty}(\theta) = \lim_{T \to \infty} \frac{\mathcal{I}_T(\theta)}{T} \approx \frac{1}{2} \left( \frac{\sigma^2}{\sigma^2 + \omega^2} \right)^2. $$

In conclusion, this informal analysis reveals an asymptotic error equivalent to

$$ \frac{1}{\sqrt{T}} \sqrt{\mathcal{I}_{\infty}(\theta)^{-1}} \approx \frac{\sqrt{2}}{\sqrt{T}} \left( 1 + \frac{\omega^2}{\sigma^2} \right), $$

which is coherent with the dependency we identified in Theorem 2. □

# D GLOSSARY

## D.1 NOTATIONS

For any integer $n$, let $[n] = \{1, ..., n\}$. The symbol $1_{\{\dots\}}$ stands for an indicator function. When dealing with random variables, we write $\mathbb{P}(X = x)$ for a probability density, $\mathbb{E}[X]$ for an expectation, $\mathrm{Var}[X]$ for a variance (scalar of vector) and $\mathrm{Cov}[X, Y]$ for a covariance (scalar or matrix). The symbols $\mathcal{B}(p)$ and $\mathcal{N}(\mu, \Sigma)$ denote a Bernoulli distribution and a (possibly multivariate) Gaussian distribution. When we write $\log(x)$, we mean the natural (base-e) logarithm.

Given a real number $a$, we denote by $|a|$ its absolute value. Given a vector $x$, we denote by $\|x\|_2$ (resp. $\|x\|_1$, $\|x\|_{\infty}$, $\|x\|_0$) its Euclidean norm (resp. $\ell_1$ norm, $\ell_{\infty}$ norm, number of nonzero entries). The notation $e_i$ stands for a vector with a single non-zero coordinate at position $i$.

A matrix can be defined by its coefficients $M = (M_{i,j})_{i,j}$ or by its blocks $M = (M_{[b_1, b_2]})_{b_1, b_2}$. We write $I$ for the identity matrix, and $J_r$ for the square matrix entirely filled with zeros, except for the subdiagonal of rank $r$ which is filled with ones. The notation $\mathrm{diag}(\lambda)$ stands for the diagonal matrix with coefficients $\lambda_1, ..., \lambda_n$, while $\mathrm{bdiag}_T(M)$ stands for a block-diagonal matrix with $T$ copies of $M$ on the diagonal and zeros elsewhere. We write $\mathrm{vec}(M)$ for the column-wise flattening of matrix $M$ into a vector. When we want to apply a function elementwise, we often use notation that is standard for real numbers but not for matrices: for instance, $\sqrt{M} = (\sqrt{M_{i,j}})_{i,j}$ and $1/M = (1/M_{i,j})_{i,j}$. Given a real matrix $M$, we denote by

* $M'$ its transposition, $M^\dagger$ its Moore-Penrose pseudo-inverse and $M^{-1}$ its inverse;

* $\mathrm{Tr}(M)$ its trace and $\mathrm{det}(M)$ its determinant;

* $\lambda_{\max}(M)$ (resp. $\lambda_{\min}(M)$, $\lambda_i(M)$) its maximum (resp. minimum, $i$-th largest) eigenvalue, so that

$$ \lambda_{\max}(M) = \lambda_1(M) \geq \lambda_2(M) \cdots \geq \lambda_n(M) = \lambda_{\min}(M) $$
Since all of these prerequisites hold here, Douc, Moulines and Stoffer [11, Proposition 2.14] gives us a Central Limit Theorem for the MLE of linear Gaussian models:

$$ \sqrt{T}(\hat{\theta} - \theta) \xrightarrow[T \to \infty]{\mathcal{L}} \mathcal{N}(0, I_{\infty}(\theta)^{-1}) \quad \text{where} \quad I_{\infty}(\theta) = \lim_{T \to \infty} \frac{I_T(\theta)}{T} $$

We only have to compute the Fisher information matrix $I_T(\theta)$. The covariance matrix of $Y$ is given by Lemma B.1, but in our case the sampling matrix is constant, and we obtain the simpler (unconditional) result $\text{Cov}_{\theta}[Y] = (\sigma^2 + \omega^2)I_T + R(\theta)$, where the residual $R(\theta)$ is of order 1 in $\theta$. Indeed, our simplifying assumptions imply $\Gamma_0(\theta) = \frac{\sigma^2}{1-\theta^2}$ and therefore

$$ R(\theta) = \frac{\sigma^2}{1 - \theta^2} \begin{pmatrix} \theta^2 & \theta^1 & \theta^2 & \cdots \\ \theta^1 & \theta^2 & \theta^1 & \cdots \\ \theta^2 & \theta^1 & \theta^2 & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix} \qquad \partial_{\theta} R(\theta) = \sigma^2 \begin{pmatrix} 0 & 1 & 0 & \cdots \\ 1 & 0 & 1 & \cdots \\ 0 & 1 & 0 & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix} + \mathcal{O}(\theta). $$

The Fisher information of $Y$ with respect to $\theta$ has an explicit formula [29, Section 3.5]:

$$ \begin{aligned} I_T(\theta) &= \frac{1}{2} \text{Tr} \left[ \text{Cov}_{\theta}[Y]^{-1} \partial_{\theta} \text{Cov}_{\theta}[Y] \text{Cov}_{\theta}[Y]^{-1} \partial_{\theta} \text{Cov}_{\theta}[Y] \right] \\ &= \frac{1}{2} \text{Tr} \left[ \left( I + \frac{R(\theta)}{\sigma^2 + \omega^2} \right)^{-1} \frac{\partial_{\theta} R(\theta)}{\sigma^2 + \omega^2} \left( I + \frac{R(\theta)}{\sigma^2 + \omega^2} \right)^{-1} \frac{\partial_{\theta} R(\theta)}{\sigma^2 + \omega^2} \right]. \end{aligned} $$

If assume $\theta$ is small and perform a Taylor expansion, we get:

$$ I_T(\theta) \approx \frac{1}{2(\sigma^2 + \omega^2)^2} \text{Tr} \left[ (\partial_{\theta} R(\theta))^2 \right]. $$

Incidentally, we also note that at the lowest order in $\theta$,

$$ \text{Tr}[(\partial_{\theta} R(\theta))^2] = \|\partial_{\theta} R(\theta)\|_{F}^{2} \approx 2\sigma^4(T-1). $$

Which gives us an approximate information matrix for $T$ steps:

$$ I_T(\theta) \approx \frac{\text{Tr}[(\partial_{\theta} R(\theta))^2]}{2(\sigma^2 + \omega^2)^2} \approx \frac{T}{2} \left( \frac{\sigma^2}{\sigma^2 + \omega^2} \right)^2. $$

Taking the temporal limit yields:

$$ I_{\infty}(\theta) = \lim_{T \to \infty} \frac{I_T(\theta)}{T} \approx \frac{1}{2} \left( \frac{\sigma^2}{\sigma^2 + \omega^2} \right)^2. $$

In conclusion, this informal analysis reveals an asymptotic error equivalent to

$$ \frac{1}{\sqrt{T}} \sqrt{I_{\infty}(\theta)^{-1}} \approx \frac{\sqrt{2}}{\sqrt{T}} \left( 1 + \frac{\omega^2}{\sigma^2} \right), $$

which is coherent with the dependency we identified in Theorem 3.2. □
• $s_{\max}(M)$ (resp. $s_{\min}(M)$, $s_i(M)$) its maximum (resp. minimum, i-th largest) singular value;

• $\|M\|_1 = \sup \frac{\|Mx\|_1}{\|x\|_1} = \max_j \sum_i |M_{i,j}|$ its operator $\ell_1$ norm, which is the maximum $\ell_1$ norm of a column of $M$;

• $\|M\|_2 = \sup \frac{\|Mx\|_2}{\|x\|_2} = |s_{\max}(M)| = \sqrt{\lambda_{\max}(M'M)}$ its operator $\ell_2$ norm, also known as the spectral norm;

• $\|M\|_{\infty} = \sup \frac{\|Mx\|_{\infty}}{\|x\|_{\infty}} = \max_i \sum_j |M_{i,j}|$ its operator $\ell_{\infty}$ norm, which is the maximum $\ell_1$ norm of a row of $M$;

• $\|M\|_F = \|\text{vec}(M)\|_2 = \text{Tr}(M'M)$ its Frobenius norm;

• $\|M\|_{\max} = \|\text{vec}(M)\|_{\infty} = \max_{i,j} |M_{i,j}|$ the maximum absolute value of its entries;

• $\rho(M)$ its spectral radius.

See Petersen and Pedersen [2012] for a collection of inequalities relating all of these quantities. Given two real matrices $A$ and $B$, we denote by

• $A \otimes B$ their Kronecker product;

• $A \odot B$ Hadamard (elementwise) product;

• $A \succeq B$ or $A \preceq B$ the (partial) Loewner order on symmetric matrices.

## D.2 FREQUENT SYMBOLS

Here is a list of the most frequent symbols and their meaning.

Dimensions:

• $t \in [T]:$ time step

• $d \in [D]:$ dimension

State process:

• $X_t$: state process

• $\theta$: transition matrix

• $\varepsilon_t$: innovations

• $\Sigma$: covariance matrix of $\varepsilon_t$

• $\sigma_{\min}^2, \sigma_{\max}^2$: extremal eigenvalues of $\Sigma$

• $s$: sparsity level of $\theta$ (number of non-zero coefficients in each row)

• $\vartheta$: maximum $\ell_2$ norm for $\theta$

• $\Theta_s$: set of feasible values for $\theta$

• $\Gamma_h(\theta)$: covariance between $X_{t+h}$ and $X_t$

Observations:

• $\pi_t$: random sampling vector

• $\Pi_t$: diagonal random sampling matrix

• $p$: fraction of state components activated by observations
## Acknowledgments

The authors would like to thank their colleague Axel Parmentier for his collaboration and careful proofreading. Clément Mantoux, Éloïse Berthier, Maxime Godin and Pierre Marion (by alphabetical order of first names) provided more support and advice than can be described in such a constrained space. We also thank Emeline Luirard for her help with a critical Lemma, and Mathieu Besançon for his last-minute look at the draft.

We are very grateful to SNCF, especially its departments DGEX Solutions (SNCF Réseau) and Transilien (SNCF Voyageurs) for providing us with the inspiration behind this work.

Finally, the authors would like to thank the anonymous referees and the associate editor for their useful feedback and the time they devoted to the paper.

## Funding

Guillaume Dalle (ENPC) was partially funded by SNCF during his PhD work.

## Supplementary Material

### Code for the experiments

(doi: 10.1214/25-EJS2387SUPP; .zip). POVAR2.jl is a Julia package for reproducing the numerical results presented in the paper. It is supplied in a compressed format [10], but also available online [9].

## References

[1] BASU, S. and MICHAILIDIS, G. (2015). Regularized estimation in sparse high-dimensional time series models. *The Annals of Statistics* **43**. https://doi.org/10.1214/15-AOS1315 MR3357870

[2] BERNANKE, B. S., BOIVIN, J. and ELIASZ, P. (2005). Measuring the Effects of Monetary Policy: A Factor-Augmented Vector Autoregressive (FAVAR) Approach*. *The Quarterly Journal of Economics* **120** 387–422. https://doi.org/10.1162/0033553053327452

[3] BEZANSON, J., EDELMAN, A., KARPINSKI, S. and SHAH, V. B. (2017). Julia: A Fresh Approach to Numerical Computing. *SIAM Review* **59** 65–98. https://doi.org/10.1137/141000671 MR3605826

[4] BUONACCORSI, J. P. (2010). *Measurement Error: Models, Methods, and Applications*. Chapman and Hall/CRC, New York. https://doi.org/10.1201/9781420066586 MR2682774

[5] CANDES, E. and TAO, T. (2007). The Dantzig selector: Statistical estimation when p is much larger than n. *The Annals of Statistics* **35**. https://doi.org/10.1214/009053606000001523 MR2382647

[6] CAPPÉ, O., MOULINES, E. and RYDÉN, T. (2005). *Inference in Hidden Markov Models*. Springer Series in Statistics. Springer New York, New York, NY. https://doi.org/10.1007/0-387-28982-8 MR2159833
• $\mathcal{T}$: transition matrix for Markov sampling

• $a, b$: transition probabilities for Markov sampling

• $\chi$: minimum distance between $a$ or $b$ and $\{0, 1\}$ (considered constant)

• $Y_t$: observations

• $\eta_t$: noise

• $\omega^2$: variance of $\eta_t$

**Estimation:**

• $h$: covariance time lag

• $h_0$: minimum covariance time lag for transition estimation

• $S(h)$: scaling matrix for covariance estimation

• $pq_u$: smallest coefficient of the scaling matrix

**Other:**

• $g$: standard Gaussian vector

• $\Psi_e$ (resp. $\Psi_\eta$): link between $X$ (resp. $\eta$) and a standard Gaussian vector

• $L$: random bilinear form

• $u$: threshold in concentration inequalities

• $\delta$: small probability

• $Q_{\Pi}$: constant term in the conditional variance of $Y$

• $R_{\Pi}(\theta)$: varying term in the conditional variance of $Y$

• $\Delta_{\Pi}(\theta)$: deviation from the identity

• $\gamma_\ell$ (resp. $\gamma_u(\theta)$): signal-to-noise ratio in the lower bound (resp. the upper bound)
[7] COVER, T. M. and THOMAS, J. A. (2006). *Elements of information theory*, 2 ed. Wiley-Interscience, Hoboken, N.J. MR2239987

[8] DALLE, G. (2022). Machine learning and combinatorial optimization algorithms, with applications to railway planning, PhD thesis, École des Ponts ParisTech.

[9] DALLE, G. (2025). gdalle/POVAR2.jl: v0.1.0. Zenodo. https://doi.org/10.5281/zenodo.15295941

[10] DALLE, G. DE CASTRO, Y. (2025). Supplement to “Minimax estimation of partially-observed vector autoregressions”. https://doi.org/10.1214/25-EJS2387SUPP

[11] DOUC, R., MOULINES, E. and STOFFER, D. (2013). *Nonlinear Time Series: Theory, Methods and Applications with R Examples*. Chapman and Hall/CRC, New York. https://doi.org/10.1201/b16331 MR3289095

[12] DOUCET, A., GODSILL, S. and ANDRIEU, C. (2000). On sequential Monte Carlo sampling methods for Bayesian filtering. *Statistics and Computing* **10** 197–208. https://doi.org/10.1023/A:1008935410038

[13] DUBHASHI, D. P. and PANCONESI, A. (2009). *Concentration of Measure for the Analysis of Randomized Algorithms*. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511581274 MR2547432

[14] DUCHI, J. (2007). Derivations for linear algebra and optimization.

[15] DUCHI, J. (2019). Information Theory and Statistics.

[16] DUNNING, I., HUCHETTE, J. and LUBIN, M. (2017). JuMP: A Modeling Language for Mathematical Optimization. *SIAM Review* **59** 295–320. https://doi.org/10.gftshn MR3646493

[17] HAN, F., LU, H. and LIU, H. (2015). A Direct Estimation of High Dimensional Stationary Vector Autoregressions. *Journal of Machine Learning Research* **16** 3115–3150. MR3450535

[18] HORN, R. A. and JOHNSON, C. R. (1991). *Topics in Matrix Analysis*. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511840371 MR1091716

[19] HORN, R. A. and JOHNSON, C. R. (2012). *Matrix Analysis*, 2 ed. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9781139020411 MR2978290

[20] HUANGFU, Q. and HALL, J. A. J. (2018). Parallelizing the dual revised simplex method. *Mathematical Programming Computation* **10** 119–142. https://doi.org/10.1007/s12532-017-0130-5 MR3773090

[21] JALALI, A. and WILLETT, R. (2018). Missing Data in Sparse Transition Matrix Estimation for Sub-Gaussian Vector Autoregressive Processes. https://doi.org/10.48550/arXiv.1802.09511

[22] KALMAN, R. E. (1960). A New Approach to Linear Filtering and Prediction Problems. *Journal of Basic Engineering* **82** 35–45. https://doi.org/10.1115/1.3662552 MR3931993

[23] KOCK, A. B. and CALLOT, L. (2015). Oracle inequalities for high dimensional vector autoregressions. *Journal of Econometrics* **186** 325–344. https://doi.org/10.1016/j.jeconom.2015.02.013 MR3343790
[24] LIN, J. and MICHAILIDIS, G. (2020). Regularized Estimation of High-dimensional Factor-Augmented Vector Autoregressive (FAVAR) Models. *Journal of Machine Learning Research* **21** 1–51. MR4119185

[25] LITTLE, R. J. A. and RUBIN, D. B. (2020). *Statistical analysis with missing data*, 3 ed. *Wiley series in probability and statistics*. Wiley, Hoboken, NJ. MR1925014

[26] LOH, P.-L. and WAINWRIGHT, M. J. (2012). High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity. *The Annals of Statistics* **40** 1637–1664. https://doi.org/10/ggx5bj MR3015038

[27] LÜTKEPOHL, H. (2005). *New Introduction to Multiple Time Series Analysis*. Springer Berlin Heidelberg, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27752-1 MR2172368

[28] LÜTKEPOHL, H. (2013). Vector autoregressive models. *Handbook of Research Methods and Applications in Empirical Macroeconomics*.

[29] MALAGÒ, L. and PISTONE, G. (2015). Information Geometry of the Gaussian Distribution in View of Stochastic Optimization. In *Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII* 150–162. ACM, Aberystwyth United Kingdom. https://doi.org/10.1145/2725494.2725510 MR3388148

[30] MELNYK, I. and BANERJEE, A. (2016). Estimating Structured Vector Autoregressive Models. In *Proceedings of The 33rd International Conference on Machine Learning* 830–839. PMLR.

[31] RAO, M., JAVIDI, T., ELDAR, Y. C. and GOLDSMITH, A. (2017a). Estimation in autoregressive processes with partial observations. In *2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)* 4212–4216. https://doi.org/10.1109/ICASSP.2017.7952950

[32] RAO, M., JAVIDI, T., ELDAR, Y. C. and GOLDSMITH, A. (2017b). Fundamental estimation limits in autoregressive processes with compressive measurements. In *2017 IEEE International Symposium on Information Theory (ISIT)* 2895–2899. https://doi.org/10.1109/ISIT.2017.8007059

[33] SEN, P. K. (1968). Estimates of the Regression Coefficient Based on Kendall's Tau. *Journal of the American Statistical Association* **63** 1379–1389. https://doi.org/10/gfxz87 MR0258201

[34] SHUMWAY, R. H. and STOFFER, D. S. (1982). An Approach to Time Series Smoothing and Forecasting Using the EM Algorithm. *Journal of Time Series Analysis* **3** 253–264. https://doi.org/10.1111/j.1467-9892.1982.tb00349.x MR0716699

[35] SIMCHOWITZ, M., MANIA, H., TU, S., JORDAN, M. I. and RECHT, B. (2018). Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification. In *Proceedings of the 31st Conference On Learning Theory* 439–473. PMLR.

[36] TIBSHIRANI, R. (1996). Regression Shrinkage and Selection Via the Lasso. *Journal of the Royal Statistical Society: Series B (Methodological)* **58** 267–288. https://doi.org/10.1111/j.2517-6161.1996.tb02080.x MR1379242

[37] TSYBAKOV, A. B. (2009). *Introduction to Nonparametric Estimation*. Springer Series in Statistics. Springer New York, New York, NY. https://doi.org/10.1007/b13794 MR2724359
[38] VERSHYNIN, R. (2018). *High-Dimensional Probability: An Introduction with Applications in Data Science*. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge. https://doi.org/10.1017/9781108231596 MR3837109

[39] WAINWRIGHT, M. J. (2019). *High-Dimensional Statistics: A Non-Asymptotic Viewpoint*. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge. https://doi.org/10.1017/9781108627771 MR3967104