### E.3. Proof of Proposition D.5

For simplicity, we write in this proof $\Theta := \Theta(\tilde{P}, Q)$ and $\Theta(\overline{P}') := \Theta(\overline{P}', Q)$. Without loss of generality, we assume that the rows of $\Theta$ are already ordered according to the oracle order so that $\Theta$ is bi-isotonic.

First, the following lemma states that, the first singular value of $(\Theta - \overline{\Theta})$ is, up to polylog- arithmic terms, of the same order as its Frobenius norm. This is mainly due to the fact that the entries of $\Theta$ lies in $[0, \sqrt{r}]$ and that $\Theta$ is a bi-isotonic matrix.

**Lemma E.4.** Assume that $\|\Theta - \overline{\Theta}\|_F \ge 2\zeta$. For any sets $\tilde{P}$ and $Q$, we have

$$ \|\Theta - \overline{\Theta}\|_{\text{op}}^2 \ge \frac{1}{16 \log^2(\text{nd}/\zeta_-)} \|\Theta - \overline{\Theta}\|_F^2 . $$

$$ \text{Now, write } \hat{v} = \arg \max_{\|v\|_2 \le 1} \left[ \|v^T(Z^{(1)} - \bar{Z}^{(1)})\|_2^2 - \frac{1}{2} \|v^T(Z^{(1)} - \bar{Z}^{(1)} - Z^{(2)} + \bar{Z}^{(2)})\|_2^2 \right]. $$

**Lemma E.5.** Fix any $\delta \in (0, 1)$. If

$$ \|\Theta - \overline{\Theta}\|_{\text{op}}^2 \ge 1600\zeta^2 \left[ \sqrt{|Q|(5|\tilde{P}| + \log(6/\delta))} + 7|\tilde{P}| + 2\log(6/\delta) \right], \quad (77) $$

then, with probability higher than $1 - \delta$, we have

$$ \|\hat{v}^T (\Theta - \overline{\Theta})\|_2^2 \ge \frac{1}{2} \|\Theta - \overline{\Theta}\|_{\text{op}}^2 . $$

In light of Lemma E.4 and Condition (62), the Condition (77) in Lemma E.5 is valid. Consequently, there exists an event of probability higher than $1 - \delta$ such that

$$ \|\hat{v}^T (\Theta - \overline{\Theta})\|_2^2 \ge \frac{1}{32 \log^2(\text{nd}/\zeta_-)} \|\Theta - \overline{\Theta}\|_F^2 . \quad (78) $$

Next, we show that a thresholded version of $\hat{z} = (Z^{(3)} - \bar{Z}^{(3)})^T \hat{v}$ is almost aligned with $z^* = (\Theta - \overline{\Theta})^T \hat{v}$. We define the sets $S^* \subset Q$ and $\hat{S} \subset Q$ of blocks of questions by

$$ S^* = \{l \in Q : |z_l^*| \ge 3\zeta\sqrt{2\log(2|Q|/\delta)}\}; \quad \hat{S} = \{l \in Q : |\hat{z}_l| \ge 2\zeta\sqrt{2\log(2|Q|/\delta)}\}. $$

$S^*$ stands for the collection of blocks of questions $l$ such that $z_l^*$ is large whereas $\hat{S}$ is the collection of blocks $l$ with large $\hat{z}_l$. Finally, we consider the vectors $w^*$ and $\hat{w}$ defined as thresholded versions of $z^*$ and $\hat{z}$ respectively, that is $w_i^* = z_i^* 1_{i \in S^*}$ and $\hat{w}_i = \hat{z}_i 1_{i \in \hat{S}}$. Note that, up to the sign, $\hat{w}$ stands for the active coordinates computed in **DoubleTrisection** – **PCA**.

We write $v$ for any unit vector in $\mathbb{R}^{|\tilde{P}|}$. Since the noise matrix $N^{(2)}$ is made of independent $\zeta$-subGaussian random variables, it follows that $(v^T(N^{(3)} - \overline{N}^{(3)}))_l$ is a $\zeta$-subGaussian random variables. Hence, we deduce that, for any fixed matrix $\Theta$, subsets $\tilde{P}$ and $Q$, and any unit vector $v$, we have

$$ \mathbb{P} \left[ \max_{l \in Q} \left| (v^T(N^{(3)} - \overline{N}^{(3)}))_l \right| \le \zeta \sqrt{2 \log(2|Q|/\delta)} \right] \ge 1 - \delta . $$

Observe that $\hat{z} = z^* + \hat{v}^T(N^{(3)} - \overline{N}^{(3)})$. Conditioning on $\hat{v}$, we deduce that, on an event of probability higher than $1 - \delta$, we have

$$ \|\hat{z} - z^*\|_{\infty} \le \zeta \sqrt{2 \log(2|Q|/\delta)}. \quad (79) $$
Under this event, we have $S^* \subset \hat{S}$ and for $l \in \hat{S}$, we have $z_l^* / \hat{z}_l \in [1/2, 2]$. Next, we shall prove that, under this event, $\hat{v}^T(\Theta - \bar{\Theta})\hat{w} / \|\hat{w}\|_2$ is large (in absolute value):

$$|\hat{v}^T(\Theta - \bar{\Theta})\hat{w}| = |(z^*)^T\hat{w}| = \sum_{l \in \hat{S}} z_l^* \hat{z}_l \ge \frac{2}{5} \sum_{l \in \hat{S}} (z_l^*)^2 + (\hat{z}_l)^2 \ge \frac{2}{5} [\|w^*\|_2^2 + \|\hat{w}\|_2^2] \ge \frac{4}{5} \|\hat{w}\|_2 \|w^*\|_2,$$

where we used in the first inequality that $z_l^* / \hat{z}_l \in [1/2, 2]$ and in the second inequality that $S^* \subset \hat{S}$. Thus, it holds that

$$\left| \hat{v}^T(\Theta - \bar{\Theta}) \frac{\hat{w}}{\|\hat{w}\|_2} \right|^2 \ge \frac{16}{25} \|w^*\|_2^2. \qquad (80)$$

It remains to prove that $\|w^*\|_2$ is large enough. Writing $S^{*c}$ for the complementary of $S^*$ in $Q$, it holds that

$$\|w^*\|_2^2 = \|z^*\|_2^2 - \sum_{l \in S^{*c}} (z_l^*)^2, \qquad (81)$$

so that we need to upper bound the latter quantity. Write $z_{S^{*c}}^* = z^* - w^*$. Coming back to the definition of $z^*$,

$$\begin{aligned}
\left[ \sum_{l \in S^{*c}} (z_l^*)^2 \right]^2 &= \left[ \sum_{l \in S^{*c}} [\hat{v}^T(\Theta - \bar{\Theta})]_l z_l^* \right]^2 \\
&\le \| (\Theta - \bar{\Theta}) z_{S^{*c}}^* \|_2^2 = \sum_{i \in \tilde{P}} \left( \sum_{l \in S^{*c}} (\Theta_{i,l} - \bar{\theta}_l) z_l^* \right)^2 \\
&\le \frac{18 \zeta^2}{|\tilde{P}|^2} \log \left( \frac{2|Q|}{\delta} \right) \sum_{i \in \tilde{P}} \left( \sum_{l \in S^{*c}} \sum_{j \in \tilde{P}} |\Theta_{i,l} - \Theta_{j,l}| \right)^2 \\
&\le \frac{18 \zeta^2}{|\tilde{P}|^2} \log \left( \frac{2|Q|}{\delta} \right) \sum_{i \in \tilde{P}} \left( \sum_{j \in \tilde{P}} \|\Theta_{i,\cdot} - \Theta_{j,\cdot}\|_1 \right)^2 \\
&\le 18 \zeta^2 \phi_{l_1}^2 \log \left( \frac{2|Q|}{\delta} \right) \log \left( \frac{2|\tilde{P}|}{\delta} \right) |\tilde{P}| \|Q\| \\
&\le \left[ 145 \zeta^2 \log \left( \frac{2|Q||\tilde{P}|}{\delta} \right) \sqrt{|\tilde{P}| \|Q\|} \right]^2,
\end{aligned}$$

where we used the definition of $S^*$ in the third line as well as the Condition (71) in the fifth line. We recall that $\phi_{l_1} = 2(2\zeta\sqrt{2} + \bar{\beta}_{\text{tris}}) \le 29\zeta$ is defined in (60). Recall that $z^* = \hat{v}^T(\Theta - \bar{\Theta})$. Combining (78), (81), and Condition (62), we deduce that

$$\|w^*\|_2^2 \ge \frac{1}{64 \log^2(nd/\zeta_-)} \|\Theta - \bar{\Theta}\|_F^2,$$

which, together with (80), yields

$$\left\| (\Theta - \bar{\Theta}) \frac{\hat{w}}{\|\hat{w}\|_2} \right\|_2^2 \ge \left| \hat{v}^T(\Theta - \bar{\Theta}) \frac{\hat{w}}{\|\hat{w}\|_2} \right|^2 \ge \frac{1}{100 \log^2(nd/\zeta_-)} \|\Theta - \bar{\Theta}\|_F^2.$$

Write $\hat{w}^{(1)}$ and $\hat{w}^{(2)}$ the positive and negative parts of $\hat{w}$ respectively so that $\hat{w} = \hat{w}^{(1)} - \hat{w}^{(2)}$ and $\hat{w}^+ = \hat{w}^{(1)} + \hat{w}^{(2)}$. We obviously have $\|\hat{w}\|_2 = \|\hat{w}^+\|_2$. Besides, if the rows of $\Theta$ are ordered according to the oracle permutation, then $(\Theta - \bar{\Theta})\hat{w}^{(1)}$ and $(\Theta - \bar{\Theta})\hat{w}^{(2)}$ are increasing vectors
with mean zero. It then follows from Harris' inequality that these two vectors have a nonegative inner product. We have proved that

$$ \left\| (\Theta - \bar{\Theta}) \frac{\hat{w}^+}{\|\hat{w}^+\|_2} \right\|_2^2 \ge \left\| (\Theta - \bar{\Theta}) \frac{\hat{w}}{\|\hat{w}\|_2} \right\|_2^2 \ge \frac{1}{100 \log^2(\mathrm{nd}/\zeta_-)} \|\Theta - \bar{\Theta}\|_F^2 . \quad (82) $$

Equipped with this bound, we are now in position to show that the set $\bar{P}'$ of experts obtained from $\tilde{P}$ when applying the pivoting algorithm with $\hat{w}^+/\|\hat{w}^+\|_2$ has a much smaller variance.

By Lemma C.1, there exists an event of probability higher than $1 - \delta$ such that

$$ \max_{i,j \in \bar{P}'} \left| \langle \Theta(\bar{P}')_{i,j}, -\Theta(\bar{P}')_{j,i}, \frac{\hat{w}^+}{\|\hat{w}^+\|_2} \rangle \right| \le \phi_{l_1} \sqrt{\log\left(\frac{2|\bar{P}|}{\delta}\right)}, $$

where we recall that $\phi_{l_1} = 2(2\zeta\sqrt{2} + \bar{\beta}_{\mathrm{tris}})$. By convexity, it follows that

$$ \left\| (\Theta(\bar{P}') - \bar{\Theta}(\bar{P}')) \frac{\hat{w}^+}{\|\hat{w}^+\|_2} \right\|_2^2 \le \phi_{l_1}^2 \log\left(\frac{2|\bar{P}|}{\delta}\right) |\bar{P}'| \le \phi_{l_1}^2 \log\left(\frac{2|\bar{P}|}{\delta}\right) |\bar{P}| . $$

In light of Condition (62), this quantity is small compared to $\|\Theta - \bar{\Theta}\|_F^2$:

$$ \| (\Theta(\bar{P}') - \bar{\Theta}(\bar{P}')) \frac{\hat{w}^+}{\|\hat{w}^+\|_2} \|_2^2 \le \frac{1}{200 \log^2(\mathrm{nd}/\zeta_-)} \|\Theta - \bar{\Theta}\|_F^2, \quad (83) $$

which together with (82) leads to

$$ \| (\Theta - \bar{\Theta}) \frac{\hat{w}^+}{\|\hat{w}^+\|_2} \|_2^2 - \| (\Theta(\bar{P}') - \bar{\Theta}(\bar{P}')) \frac{\hat{w}^+}{\|\hat{w}^+\|_2} \|_2^2 \ge \frac{1}{200 \log^2(\mathrm{nd}/\zeta_-)} \|\Theta - \bar{\Theta}\|_F^2 . \quad (84) $$

Since $\bar{P}' \subset \tilde{P}$, we deduce that, for any vector $w' \in \mathbb{R}^q$, we have $\| (\Theta - \bar{\Theta})w' \|_2^2 \ge \| (\Theta(\bar{P}') - \bar{\Theta}(\bar{P}'))w' \|_2^2$. It then follows from the Pythagorean theorem that

$$ \|\Theta - \bar{\Theta}\|_F^2 - \|\Theta(\bar{P}') - \bar{\Theta}(\bar{P}')\|_F^2 \ge \|(\Theta - \bar{\Theta})\frac{\hat{w}^+}{\|\hat{w}^+\|_2}\|_2^2 - \|(\Theta(\bar{P}') - \bar{\Theta}(\bar{P}'))\frac{\hat{w}^+}{\|\hat{w}^+\|_2}\|_2^2. $$

Then, together with (84), we arrive at

$$ \|\Theta(\bar{P}') - \bar{\Theta}(\bar{P}')\|_F^2 \le \left(1 - \frac{1}{200 \log^2(\mathrm{nd}/\zeta)}\right) \|\Theta - \bar{\Theta}\|_F^2. $$

*Proof of Lemma E.4.* The proof mainly relies on a discretisation argument. Given any $a \in \mathbb{R}$ and any matrix $U$, we define the matrix $[U]_a^{\mathrm{thres}}$ by $([U]_a^{\mathrm{thres}})_{i,j} = U_{i,j} \mathbf{1}\{U_{i,j} \in (a, 2a]\}$. If $a$ is negative, then the interval should be understood as $[2a, a)$. Recall that all the entries of $\Theta - \bar{\Theta}$ lie in $[-\sqrt{r}, \sqrt{r}]$. This allows us to decompose this matrix as follows

$$ r^{-1/2}(\Theta - \bar{\Theta}) = \sum_{i \in \mathbb{N}^*} [r^{-1/2}(\Theta - \bar{\Theta})]_{2^{-i}}^{\mathrm{thres}} + [r^{-1/2}(\Theta - \bar{\Theta})]_{-2^{-i}}^{\mathrm{thres}}. $$

All the matrices in this decomposition have disjoint support. For all $i > \log_2(\mathrm{nd}/\zeta)$, all the entries of the discretised matrices in the decomposition are smaller than $\zeta(\mathrm{nd})^{-1}$. Since $|\tilde{P}| = p \le n$ and $|Q| = q \le d/r$, this implies that

$$ \left\| \sum_{i \in \mathbb{N}^*, i > \log_2(\mathrm{nd}/\zeta)} [r^{-1/2}(\Theta - \bar{\Theta})]_{2^{-i}}^{\mathrm{thres}} + [r^{-1/2}(\Theta - \bar{\Theta})]_{-2^{-i}}^{\mathrm{thres}} \right\|_F^2 \le \zeta^2 \frac{\mathrm{nd}}{(\mathrm{nd})^2 r} \le \frac{\zeta^2}{r}. $$
Coming back to the previous bound, we arrive at

$$ \|r^{-1/2}(\Theta - \bar{\Theta})\|_F^2 \le \sum_{i \in \mathbb{N}^*, i \le \log_2(\text{nd}/\zeta)} \|[r^{-1/2}(\Theta - \bar{\Theta})]_{2^{-i}}^{\text{thres}}\|_F^2 + \|[r^{-1/2}(\Theta - \bar{\Theta})]_{-2^{-i}}^{\text{thres}}\|_F^2 + \frac{\zeta^2}{r} $$

As we assume that $\|\Theta - \bar{\Theta}\|_F \ge 2\zeta \ge 2\zeta/\sqrt{r}$,

$$ \|r^{-1/2}(\Theta - \bar{\Theta})\|_F^2 \le \frac{4}{3} \sum_{i \in \mathbb{N}^*, i \le \log_2(\text{nd}/\zeta)} \|[r^{-1/2}(\Theta - \bar{\Theta})]_{2^{-i}}^{\text{thres}}\|_F^2 + \|[r^{-1/2}(\Theta - \bar{\Theta})]_{-2^{-i}}^{\text{thres}}\|_F^2. $$

Hence, there exists an integer $i_0 \in [1, \log_2(\text{nd}/\zeta)]$ such that

$$ \frac{3\|\Theta - \bar{\Theta}\|_F^2}{8r \log_2(\text{nd}/\zeta)} \le \|[r^{-1/2}(\Theta - \bar{\Theta})]_{2^{-i_0}}^{\text{thres}}\|_F^2 \lor \|[r^{-1/2}(\Theta - \bar{\Theta})]_{-2^{-i_0}}^{\text{thres}}\|_F^2. $$

Assume w.l.o.g. that, for this $i_0 \le \log_2(\text{nd}/\zeta)$, we have

$$ \frac{3\|\Theta - \bar{\Theta}\|_F^2}{8r \log_2(\text{nd}/\zeta)} \le \|[r^{-1/2}(\Theta - \bar{\Theta})]_{2^{-i_0}}^{\text{thres}}\|_F^2. $$

Now, we define a different discretised version. For a matrix $U$ and some $a \in \mathbb{R}^+$, let $[U]_a$ be defined by $([U]_a)_{ij} = (a\mathbf{1}\{U_{i,j} \ge a\})_{i,j}$. We readily deduce that

$$ \|\Theta - \bar{\Theta}\|_F^2 \le \frac{32}{3} r \log_2(\text{nd}/\zeta) \|[r^{-1/2}(\Theta - \bar{\Theta})]_{2^{-i_0}}\|_F^2. \quad (85) $$

The entries of the matrix $[r^{-1/2}(\Theta - \bar{\Theta})]_{2^{-i_0}}$ lie in $\{0, 2^{-i_0}\}$. Up to a permutation of the rows of $\Theta$, we can assume that each column of $[r^{-1/2}(\Theta - \bar{\Theta})]_{2^{-i_0}}$ is isotonic. One can easily check that a matrix that only takes two values and such that each column is isotonic can be transformed into a bi-isotonic matrix by applying a suitable permutation $\pi_0$ to its columns. We denote $B$ the corresponding permuted matrix. Recall that we denote $p$ and $q$ the dimensions of $B$. Then, define the function $\phi: [p] \to \{0, \dots, q\}$ such that $\phi(i)$ is the number of non-zero entries in the $(p-i+1)$-th row of $B$. Since $B$ is bi-isotonic, the function $\phi$ is non-increasing. Besides, we have

$$ \sum_{i=1}^{p} \phi(i) = 2^{i_0} \sum_{i,j} B_{i,j} = 2^{2i_0} \sum_{i,j} B_{i,j}^2 = 2^{2i_0} \|B\|_F^2. $$

**Lemma E.6.** Let $d_1$ and $d_2$ be two positive integers and consider a non-increasing function $f: [d_1] \to \mathbb{R}_+$. Then, there exists $m \in [d_1]$ such that $\sum_{i=1}^{d_1} f(i) \le \log(ed_1)mf(m)$.

Applying this lemma to $\phi$, we deduce that, for some $m \in [p]$, we have

$$ 2^{2i_0} \|B\|_F^2 \le \log ep m\phi(m). \quad (86) $$

Since $\phi(m)$ is the number of non-zero entries on the $p+1-m$-th row of $B$, since $B$ is bi-isotonic and since $B$ only takes two values, this implies that $B$ contains in the lower right a rectangle of size $m \times \phi(m)$ with value $2^{-i_0}$. Define the vector $u \in \mathbb{R}^p$ such that $u_i = m^{-1/2}$ if $i \ge p-m+1$ and $u_i = 0$, otherwise. Define also the vector $v \in \mathbb{R}^q$ such $v_j = 1/\sqrt{\phi(m)}$ if $j \ge q - \phi(m) + 1$, and $v_j = 0$ otherwise. It follows from these definitions that $u^T B v = 2^{-i_0} \sqrt{m\phi(m)}$. Recall that $[r^{-1/2}(\Theta - \bar{\Theta})]_{2^{-i_0}}$ corresponds to a row and column permutation of $B$. Hence, there exist two permutations $\pi_1$ and $\pi_2$ such that

$$ u_{\pi_1}^T [r^{-1/2}(\Theta - \bar{\Theta})]_{2^{-i_0}} v_{\pi_2} = u^T B v. $$
By construction, the entries of $\Theta - \bar{\Theta}$ are higher than $2^{-i_0}$ for all entries such that $(u_{\pi_1})_i \neq 0$ and $(v_{\pi_1})_j \neq 0$. We deduce that

$$ \|\Theta - \bar{\Theta}\|_{\text{op}} \geq \sqrt{r} u_{\pi_1}^T r^{-1/2} (\Theta - \bar{\Theta}) v = \sqrt{r} 2^{-i_0} \sqrt{m\phi(m)} \geq \frac{\sqrt{r}}{\sqrt{\log ep}} \|B\|_F . $$

Finally, we come back to (85) to conclude that $\|\Theta - \bar{\Theta}\|_{\text{op}} \geq [32 \log ep \log_2(\text{nd}/\zeta)/3]^{-1/2} \|\Theta - \bar{\Theta}\|_F$, where we recall that $\zeta_-$ < $\zeta$. $\square$

**Proof of Lemma E.6.** Define $a = \sup_{m=1}^{d_1} m f(m)$. As a consequence, we have $f(m) \leq a/m$. This implies that

$$ \sum_{i=1}^{d_1} f(i) \leq \sum_{i=1}^{d_1} \frac{a}{i} \leq a \log(ed_1) . $$

We have proved that $\log(ed_1) \sup_{m=1}^{d_1} m f(m) \geq \sum_{i=1}^{d_1} f(i)$. $\square$

**Proof of Lemma E.5.** We start with the two following lemmas. For short, we write $p = |\bar{P}|$ and $q = |Q|$ in this proof.

**Lemma E.7.** Let $N'$ denote a random $d_1 \times d_2$ matrix whose entries follow independent, centered and $\zeta$-subGaussian distributions. Let $\Omega \subset \mathbb{R}^{d_2}$ be a subspace of dimension $d'_2$. With probability larger than $1 - \delta$, one has

$$ \sup_{u \in \mathbb{R}^{d_1}, v \in \Omega: \|u\|_{2} \leq 1, \|v\|_{2} \leq 1} |u^T(N' - \bar{N})v| \leq 10\zeta\sqrt{d_1 + d'_2 + \log(2/\delta)}, $$

where $\bar{N}' = d_1^{-1} \mathbf{1}_{d_1} \mathbf{1}_{d_1}^T N'$ is made of the mean row of $N'$.

**Lemma E.8.** Let $N'$ be a random $d_1 \times d_2$ matrix whose entries follow independent, centered and $\zeta$-subGaussian distributions. It holds with probability larger than $1 - \delta$ that

$$ \sup_{u \in \mathbb{R}^{d_1}: \|u\|_{2} \leq 1} \|u^T(N' - \bar{N})\|_{2}^{2} - \mathbb{E}\|u^T(N' - \bar{N})\|_{2}^{2} \leq 64\zeta^{2} \left[ \sqrt{d_2(5d_1 + \log(2/\delta)) + (5d_1 + \log(2/\delta))} \right]. $$

We have

$$ Z^{(1)} - \bar{Z}^{(1)} = \Theta - \bar{\Theta} + N^{(1)} - \bar{N}^{(1)}, $$

so that, for any $v \in \mathbb{R}^p$,

$$ \|v^T(Z^{(1)} - \bar{Z}^{(1)})\|_2^2 = \|v^T(\Theta - \bar{\Theta})\|_2^2 + \|v^T N^{(1)} - v^T \bar{N}^{(1)}\|_2^2 + 2\langle v^T N^{(1)} - v^T \bar{N}^{(1)}, v^T(\Theta - \bar{\Theta}) \rangle, $$

which, in turn, implies that

$$ \begin{aligned} & \|v^T(Z^{(1)} - \bar{Z}^{(1)})\|_2^2 - \|v^T(\Theta - \bar{\Theta})\|_2^2 - \mathbb{E}[\|v^T N^{(1)} - v^T \bar{N}^{(1)}\|_2^2] \leq \\ & \|v^T N^{(1)} - v^T \bar{N}^{(1)}\|_2^2 - \mathbb{E}[\|v^T N^{(1)} - v^T \bar{N}^{(1)}\|_2^2] + 2|\langle v^T N^{(1)} - v^T \bar{N}^{(1)}, v^T(\Theta - \bar{\Theta}) \rangle|. \end{aligned} \quad (87) $$

Write $W \subset \mathbb{R}^q$ for the image of $(\Theta - \bar{\Theta})^T$. Then, we apply Lemma E.7 to derive that

$$ \begin{aligned} \sup_{v \in \mathbb{R}^p: \|v\|_{2} \leq 1} & \|v^T(N^{(1)} - \bar{N}^{(1)}), v^T(\Theta - \bar{\Theta})\| \leq \|\Theta - \bar{\Theta}\|_{\text{op}} \sup_{v \in \mathbb{R}^p: \|v\|_{2} \leq 1, u \in W: \|u\|_{2} \leq 1} |v^T(N^{(1)} - \bar{N}^{(1)})u| \\ & \leq 10\zeta \|\Theta - \bar{\Theta}\|_{\text{op}} \sqrt{2p + \log(6/\delta)}, \end{aligned} \quad (88) $$
with probability higher than $1 - \delta/3$ since the dimension of $W$ is no larger than $p$. We deduce from Lemma E.8 that, with probability higher than $1 - \delta/3$, we have

$$ \sup_{v \in \mathbb{R}^p: \|v\|_2 \le 1} \left\| \|v^T(N^{(1)} - \bar{N}^{(1)})\|_2^2 - \mathbb{E}\|v^T(N^{(1)} - \bar{N}^{(1)})\|_2^2 \right\| \le 64\zeta^2 \left[ \sqrt{q(5p + \log(6/\delta))} + 5p + \log(6/\delta) \right]. $$

Together with (87) and (88), we have that with probability larger than $1 - 2\delta/3$,

$$ \sup_{v \in \mathbb{R}^p: \|v\|_2 \le 1} \left| \|v^T(Z^{(1)} - \bar{Z}^{(1)})\|_2^2 - \|v^T(\Theta - \bar{\Theta})\|_2^2 - \mathbb{E}\|v^T N^{(1)} - v^T \bar{N}^{(1)}\|_2^2 \right| \\ \le 10\zeta \|\Theta - \bar{\Theta}\|_{\text{op}} \sqrt{2p + \log(6/\delta)} + 64\zeta^2 \left[ \sqrt{q(5p + \log(6/\delta))} + (5p + \log(6/\delta)) \right]. $$

In the same way, we have that, with probability larger than $1 - \delta/3$,

$$ \sup_{v \in \mathbb{R}^p: \|v\|_2 \le 1} \left| \frac{1}{2} \|v^T(Z^{(1)} - \bar{Z}^{(1)} - Z^{(2)} + \bar{Z}^{(2)})\|_2^2 - \mathbb{E}\|v^T(N^{(1)} - \bar{N}^{(1)})\|_2^2 \right| \\ = \frac{1}{2} \sup_{v \in \mathbb{R}^p: \|v\|_2 \le 1} \left| \|v^T(Z^{(1)} - \bar{Z}^{(1)} - Z^{(2)} + \bar{Z}^{(2)})\|_2^2 - \mathbb{E}\|v^T(Z^{(1)} - \bar{Z}^{(1)} - Z^{(2)} + \bar{Z}^{(2)})\|_2^2 \right| \\ \le 128\zeta^2 \left[ \sqrt{q(5p + \log(6/\delta))} + (5p + \log(6/\delta)) \right]. $$

Putting everything together we conclude that, on an event of probability higher than $1 - 3\delta$, we have simultaneously for all $v \in \mathbb{R}^p$ with $\|v\|_2 \le 1$ that

$$ \left| \|v^T(Z^{(1)} - \bar{Z}^{(1)})\|_2^2 - \|v^T(\Theta - \bar{\Theta})\|_2^2 - \frac{1}{2} \|v^T(Z^{(1)} - \bar{Z}^{(1)} - Z^{(2)} + \bar{Z}^{(2)})\|_2^2 \right| \\ \le 10\zeta \|\Theta - \bar{\Theta}\|_{\text{op}} \sqrt{2p + \log(6/\delta)} + 192\zeta^2 \left[ \sqrt{q(3p + \log(6/\delta))} + (3p + \log(6/\delta)) \right]. $$

Since $\|\Theta - \bar{\Theta}\|_{\text{op}}^2 \ge 1600\zeta^2[\sqrt{q(5p + \log(6/\delta))} + 7p + 2\log(6/\delta)]$, we deduce that, on the same event, we have

$$ \sup_{v \in \mathbb{R}^p: \|v\|_2 \le 1} \left\| \|v^T(Z^{(1)} - \bar{Z}^{(1)})\|_2^2 - \|v^T(\Theta - \bar{\Theta})\|_2^2 - \frac{1}{2} \|v^T(Z^{(1)} - \bar{Z}^{(1)} - Z^{(2)} + \bar{Z}^{(2)})\|_2^2 \right\| \le \frac{1}{4} \|\Theta - \bar{\Theta}\|_{\text{op}}^2. $$

Writing $\psi(v) = \|v^T(Z^{(1)} - \bar{Z}^{(1)})\|_2^2 - \frac{1}{2}\|v^T(Z^{(1)} - \bar{Z}^{(1)} - Z^{(2)} + \bar{Z}^{(2)})\|_2^2$, we deduce that, for $v$ such that $\|v^T(\Theta - \bar{\Theta})\|_2^2 = \|\Theta - \bar{\Theta}\|_{\text{op}}^2$, we have $\Psi(v) \ge \frac{3}{4}\|\Theta - \bar{\Theta}\|_{\text{op}}^2$, whereas, for $v$ such that $\|v^T(\Theta - \bar{\Theta})\|_2^2 < \frac{1}{2}\|\Theta - \bar{\Theta}\|_{\text{op}}^2$, we have $\Psi(v) < \frac{3}{4}\|\Theta - \bar{\Theta}\|_{\text{op}}^2$. We conclude that $\hat{v}$ satisfies $\|\hat{v}^T(\Theta - \bar{\Theta})\|_2^2 > \frac{1}{2}\|\Theta - \bar{\Theta}\|_{\text{op}}^2$.

□

**Proof of Lemma E.7.** We start with a classical result. Variants of it can be found in random matrix textbooks (see e.g [30]). Still, we provide a simple dedicated proof below for the sake of completeness.

**Lemma E.9.** Let $N'$ be a $d_1 \times d_2$ matrix whose entries follow independent, centered, and $\zeta$-subGaussian distributions. Consider any vector subspace $\Omega \subset \mathbb{R}^{d_2}$ with dimension $d'_2$. With probability higher than $1 - \delta$, one has

$$ \sup_{u \in \mathbb{R}^{d_1}, v \in \Omega: \|u\|_2 \le 1, \|v\|_2 \le 1} |u^T N' v| \le 5\zeta \sqrt{d_1 + d'_2 + \log(1/\delta)}. $$
We have the following decomposition

$$ \sup_{\substack{u \in \mathbb{R}^{d_1}, v \in \Omega \\ \|u\|_2 \le 1, \|v\|_2 \le 1}} |u^T(N' - \bar{N}')v| \le \sup_{\substack{u \in \mathbb{R}^{d_1}, v \in \Omega \\ \|u\|_2 \le 1, \|v\|_2 \le 1}} |u^T N' v| + \sup_{\substack{u \in \mathbb{R}^{d_1}, v \in \Omega \\ \|u\|_2 \le 1, \|v\|_2 \le 1}} |u^T \bar{N}' v|. $$

The first expression in the right-hand side is handled with Lemma E.9. Regarding the second one, we observe that $\bar{N}'v$ is a constant vector. As a consequence,

$$ \sup_{\substack{u \in \mathbb{R}^{d_1}, v \in \Omega \\ \|u\|_2 \le 1, \|v\|_2 \le 1}} |u^T \bar{N}' v| \le \sqrt{d_1} \sup_{v \in \Omega} \|\bar{n}' v\|_2, $$

where $\bar{n}'$ is a $\zeta/\sqrt{d_1}$-subGaussian random vector. Then, we control this expression applying Lemma E.9 to a $1 \times d_2'$ matrix. All in all, we have proved that, with probability higher than $1 - \delta$, we have

$$ \sup_{\substack{u \in \mathbb{R}^{d_1}, v \in \Omega \\ \|u\|_2 \le 1, \|v\|_2 \le 1}} |u^T(N' - \bar{N}')v| \le 10\zeta \sqrt{(d_1 + d_2') + \log\left(\frac{2}{\delta}\right)}. $$

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

**Proof of Lemma E.9.** Let $\mathcal{U}_d(\epsilon)$ denote the $\epsilon$-covering number of the $d$-dimensional unit ball and let $\mathcal{U}_d(\epsilon)$ denote a corresponding minimal covering set. For $\Omega$ a $d_2'$-dimensional subspace of $\mathbb{R}^{d_2'}$, we also write with a slight abuse of notation $\mathcal{U}_{d_2'}(\epsilon)$ for a corresponding minimal covering set of its unit ball. Consider any $d_1 \times d_2$ matrix $W$. Write $w^* = \sup_{u: \|u\|_2 \le 1} \sup_{v \in \Omega, \|v\|_2 \le 1} |u^T W v|$ and $w = \sup_{u \in \mathcal{U}_{d_1}(1/4)} \sup_{v \in \mathcal{U}_{d_2'}(1/4)} |u^T W v|$. Given $u \in \mathbb{R}^{d_1}$, let $\pi(u)$ denote any closest point of $u$ in $\mathcal{U}_{d_1}(1/4)$. Similarly, for $v \in \Omega$, $\pi'(v)$ stands for a closest point of $v$ in $\mathcal{U}_{d_2'}(1/4)$. By triangular inequality, we have

$$ \begin{aligned} w^* &\le w + \sup_{u:\|u\|_2 \le 1} \sup_{v \in \Omega, \|v\|_2 \le 1} |u^T W v| - |\pi(u) W \pi'(v)| \\ &\le w + \sup_{u:\|u\|_2 \le 1} \sup_{v \in \Omega, \|v\|_2 \le 1} |(u^T - \pi(u)^T) W v| + |\pi(u)^T W (v - \pi'(v))| \\ &\le w + w^*/2. \end{aligned} $$

We have proven that

$$ \sup_{u:\|u\|_2 \le 1} \sup_{v \in \Omega, \|v\|_2 \le 1} |u^T W v| \le 2 \sup_{u \in \mathcal{U}_{d_1}(1/4)} \sup_{v \in \mathcal{U}_{d_2'}(1/4)} |u^T W v|. \quad (89) $$

Since $\log(\mathcal{U}_d(\epsilon)) \le d \log(3/\epsilon)$ (see e.g. [33]), we deduce from triangular inequality that, with probability higher than $1 - \delta$, we have

$$ \sup_{u \in \mathbb{R}^{d_1}, v \in \Omega: \|u\|_2 \le 1, \|v\|_2 \le 1} |u^T N' v| \le 2\zeta \sqrt{2(d_1 + d_2') \log(12) + 2 \log(1/\delta)}. $$

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

**Proof of Lemma E.8.** Relying on (89) with $W = (N' - \bar{N}')(N' - \bar{N}')^T - \mathbb{E}[(N' - \bar{N}')(N' - \bar{N}')^T]$, we derive that $\sup_{u: \|u\|_2 \le 1} \|u^T(N' - \bar{N}')\|_2^2 - \mathbb{E}\|u^T(N' - \bar{N}')\|_2^2$ is less than or equal to

$$ 2 \sup_{v \in \mathcal{U}_{d_1}(1/4)} \sup_{u \in \mathcal{U}_{d_1}(1/4)} u^T(N' - \bar{N}')(N' - \bar{N}')^T v - \mathbb{E}[u^T(N' - \bar{N}')(N' - \bar{N}')^T v] $$

As a consequence, it amounts to simultaneously control $|\mathcal{U}_{d_1}(1/4)|^2$ quadratic forms of sub-Gaussian random variables. For this purpose, we use the Hanson-Wright inequality [30]. Below we provide a version of this inequality with explicit numerical constants.
**Lemma E.10.** Let $x$ be $d$-dimensional $\zeta$-subGaussian centered random vector with independent components. For any $d \times d$ matrix $A$ and any $t > 0$, we have

$$ \mathbb{P}[x^T A x - \mathbb{E}[x^T A x] \geq 32 \zeta^2 (\|A\|_F \sqrt{t} + \|A\|_{op} t)] \leq 2e^{-t} $$

For any fixed $u$ and $v$, we interpret $u^T(N' - \overline{N}')(N' - \overline{N})^T v$ as a quadratic form of $d_1 d_2$ independent random variables where the corresponding matrix $B$ of the quadratic form satisfies $\|B\|_{op} \leq 1$ and $\|B\|_F \leq \sqrt{d_2}$. Putting everything together we deduce that, with probability higher than $1 - \delta$, we have

$$ \begin{aligned} & \sup_{u: \|u\|_2 \leq 1} \left| \|u^T(N' - \overline{N}')\|_2^2 - \mathbb{E}\|u^T(N' - \overline{N}')\|_2^2 \right| \\ & \leq 64 \zeta^2 \left[ \sqrt{d_2(2d_1 \log(12) + \log(2/\delta)) + 2d_1 \log(12) + \log(2/\delta)} \right] \\ & \leq 64 \zeta^2 \left[ \sqrt{d_2(5d_1 + \log(2/\delta)) + (5d_1 + \log(2/\delta))} \right]. \end{aligned} $$

□

**Proof of Lemma E.10.** We consider separately the diagonal terms of $A$ and the non-diagonal terms. Write $A^{-}$ for the matrix such that $A_{ij}^{-} = A_{ij} \mathbf{1}_{i \neq j}$. First, we use Section 2.8 in [22] to handle $x^T A^{-} x$. We know that

$$ \mathbb{P}[x^T A^{-} x \geq 8 \zeta^2 (\|A\|_F \sqrt{t} + \sqrt{2} \|A\|_{op} t)] \leq e^{-t}, $$

for any $t > 0$. Regarding the diagonal part, we know from Rudelson and Vershynin [23] (Step 1 of the main proof) that $\|x_i^2 - \mathbb{E}[x_i^2]\|_{\psi_1} \leq 4\zeta^2$ (see [30] for a definition of $\|\cdot\|_{\psi_1}$). Then, we are in position to apply Bernstein's inequality [3] (Theorem 2.10) to $\sum_i a_{ii} x_i^2$ with $v = (16\zeta^2)^2 \sum_i a_{ii}^2$ and $c = 16\zeta^2 \max_i |a_{ii}|$. For any $t > 0$, we have

$$ \mathbb{P}\left[\sum_{i=1}^{d} a_{ii}(x_{i}^{2} - \mathbb{E}[x_{i}^{2}]) \geq 16\zeta^{2} \left(\sqrt{2\sum_{i} a_{ii}^{2} t} + \max_{i} |a_{ii}| t\right)\right] \leq e^{-t}, $$

which implies that

$$ \mathbb{P}\left[\sum_{i=1}^{d} a_{ii}(x_{i}^{2} - \mathbb{E}[x_{i}^{2}]) \geq 16\zeta^{2} (\|A\|_{F}\sqrt{2t} + \|A\|_{op}t)\right] \leq e^{-t}. $$

We combine the two deviation inequalities and use $\|A\|_{op} \leq 2\|A\|_{op}$ to conclude that

$$ \mathbb{P}[x^T A x - \mathbb{E}[x^T A x] \geq 32 \zeta^2 [\|A\|_F \sqrt{t} + \|A\|_{op} t]] \leq 2e^{-t}. $$

□

## E.4. Proof of Corollary D.6

Let $(\overline{L}_{cp}, \overline{U}_{cp})$ denote the conservative result of **Pivot**($Z^{(1)}$, $\mathbf{1}_Q$, $\gamma$) and $\tilde{P} = \overline{P} \setminus (\overline{L}_{cp} \cup \overline{U}_{cp})$. Let $(\overline{L}_{pca}, \overline{U}_{pca}) = \text{DoubleTrisection} - \text{PCA}(\mathcal{Z}, \gamma)$ with $\mathcal{Z} = (Z^{(2)}, Z^{(3)}, Z^{(4)}, Z^{(5)})$. Here, $(Z^{(2)}, Z^{(3)}, Z^{(4)})$ restricted to the experts in $\tilde{P}$, whereas $Z^{(5)}$ is restricted to experts in $P$. Finally, we write $\overline{P}' = \tilde{P} \setminus (\overline{L}_{pca} \cup \overline{U}_{pca})$. We first prove the following intermediary result

$$ \|\Theta(\overline{P}', Q) - \overline{\Theta}(\overline{P}', Q)\|_F^2 \leq \left(1 - \frac{1}{1920 \log^2\left(\frac{nd}{\delta\zeta^-}\right)}\right) \|\Theta(\overline{P}, Q) - \overline{\Theta}(\overline{P}, Q)\|_F^2. \quad (90) $$
We consider two cases. First, we assume that $\frac{\eta}{\zeta}|\bar{P}|\sqrt{|\bar{P}|} \le \sqrt{|\bar{P}|\|Q\|} + |\bar{P}|$. Then, it follows from Equation (63) that we are in position to apply Proposition D.4 with $\phi = 120 \log^2(\frac{nd}{\delta\zeta})$. Since $\bar{P}' \subset \tilde{P}$, it follows that $\|\Theta(\bar{P}', Q) - \bar{\Theta}(\bar{P}', Q)\|_F^2 \le \|\Theta(\tilde{P}, Q) - \bar{\Theta}(\tilde{P}, Q)\|_F^2$ and (90) follows from Proposition D.4.

Now, we assume that $\sqrt{|\bar{P}|\|Q\|} + |\bar{P}| \le \frac{\eta}{\zeta}|\bar{P}|\sqrt{|\bar{P}|}$. If $\|\Theta(\tilde{P}, Q) - \bar{\Theta}(\tilde{P}, Q)\|_F^2 \le 0.5\|\Theta(\bar{P}, Q) - \bar{\Theta}(\bar{P}, Q)\|_F^2$, then the result obviously holds. Otherwise, it follows from (63) that

$$ \|\Theta(\tilde{P}, Q) - \bar{\Theta}(\tilde{P}, Q)\|_F^2 \ge 2 \cdot 10^5 \log^3 \left( \frac{6nd}{\delta\zeta_-} \right) \left[ \eta |\bar{P}| \sqrt{|\bar{P}|} \wedge \left( \sqrt{|\bar{P}|\|Q\|} + |\bar{P}| \right) \right], $$

Besides, with probability higher than $1 - \delta$, $\Theta(\tilde{P})$ is undistinguishable in $l_1$-norm by (71). Hence, we are in position to apply proposition D.5 and it follows that

$$ \begin{aligned} \|\Theta(\bar{P}', Q) - \bar{\Theta}(\bar{P}', Q)\|_F^2 &\le \left(1 - \frac{1}{200 \log^2(\frac{nd}{\delta\zeta_-})}\right) \|\Theta(\tilde{P}, Q) - \bar{\Theta}(\tilde{P}, Q)\|_F^2 \\ &\le \left(1 - \frac{1}{1920 \log^2(\frac{nd}{\delta\zeta_-})}\right) \|\Theta(\bar{P}, Q) - \bar{\Theta}(\bar{P}, Q)\|_F^2, \end{aligned} $$

which is exactly Equation (90).

It remains to conclude from Equation (90). We start from

$$ \begin{aligned} \|\Theta(\bar{P}', Q_r) - \bar{\Theta}(\bar{P}', Q_r)\|_F^2 &= \|\Theta(\bar{P}', Q) - \bar{\Theta}(\bar{P}', Q)\|_F^2 + \|\Theta(\bar{P}', Q_r \setminus Q) - \bar{\Theta}(\bar{P}', Q_r \setminus Q)\|_F^2 \\ &\le \left(1 - \frac{1}{1920 \log^2(\frac{nd}{\delta\zeta_-})}\right) \|\Theta(\bar{P}, Q) - \bar{\Theta}(\bar{P}, Q)\|_F^2 \\ &\quad + \|\Theta(\bar{P}, Q_r \setminus Q) - \bar{\Theta}(\bar{P}, Q_r \setminus Q)\|_F^2 \\ &\le \left(1 - \frac{1}{3 \cdot 10^5 \log^4(\frac{nd}{\delta\zeta_-})}\right) \|\Theta(\bar{P}, Q_r) - \bar{\Theta}(\bar{P}, Q_r)\|_F^2, \end{aligned} $$

where we used in the last line that $\|\Theta(\bar{P}, Q) - \bar{\Theta}(\bar{P}, Q)\|_F^2 \ge 1/(120 \log^2(\frac{nd}{\delta\zeta_-}))\|\Theta(\bar{P}, Q_r) - \bar{\Theta}(\bar{P}, Q_r)\|_F^2$.

### E.5. Proof of proposition D.7

For all $\tau = 0, \dots, \tau_\infty$, let $(\bar{O}_\tau, \bar{P}_\tau, \bar{I}_\tau)$ be the sets defined in **BlockSort**. Let also $(h^{\dagger\tau}, r^{\dagger\tau}) = \arg\max_{h,r} \|[\Theta(\bar{P}_\tau, Q_{cp}^*) - \bar{\Theta}(\bar{P}_\tau, Q_{cp}^*)]_{\sqrt{r\tau h}}\|_F^2$, where we recall that $Q_{cp}^*$ depends on $h$ and $r$. For simplicity, we write $Q_{cp}^{\dagger\tau} = Q_{cp}^*(h^{\dagger\tau}, r^{\dagger\tau})$. Equipped with this notation, we readily deduce from Lemma D.3 that

$$ \|M(\bar{P}_\tau) - \bar{M}(\bar{P}_\tau)\|_F^2 \le 16\zeta^2 + 96|\mathcal{R}|\|\mathcal{H}\| \left\| [\Theta(\bar{P}_\tau, Q_{cp}^{\dagger\tau}) - \bar{\Theta}(\bar{P}, Q_{cp}^{\dagger\tau})]_{\sqrt{r^{\dagger\tau}h^{\dagger\tau}}} \right\|_F^2 . \quad (91) $$

If, for some $\tau < \tau_\infty$, we have

$$ \left\| [\Theta(\bar{P}_\tau, Q_{cp}^{\dagger\tau}) - \bar{\Theta}(\bar{P}_\tau, Q_{cp}^{\dagger\tau})]_{\sqrt{r^{\dagger\tau}h^{\dagger\tau}}} \right\|_F^2 \le 4 \cdot 10^5 \zeta^2 \log^3 \left( \frac{6nd}{\delta\zeta_-} \right) \Psi(|\bar{P}_\tau|, r^{\dagger\tau}, h^{\dagger\tau}, |\bar{Q}_{cp}^{\dagger\tau}|) , \quad (92) $$

then we can fix, for any such $\tau$, $\bar{P}^\dagger = \bar{P}_\tau$, $h^\dagger = h^{\dagger\tau}$, $Q^\dagger = Q_{cp}^{\dagger\tau}$, and $r^\dagger = r^{\dagger\tau}$ so that both the properties (65) and (66) hold.
Hence, we assume henceforth that, for all $\tau$, Equation (92) does not hold and we shall arrive at a contradiction. In particular, this implies that $\|[\Theta(\bar{P}_{\tau}, Q_{\text{cp}}^{\dagger\tau}) - \bar{\Theta}(\bar{P}_{\tau}, Q_{\text{cp}}^{\dagger\tau})]_{\sqrt{r^{\dagger\tau}h^{\dagger\tau}}}\|_{F}^{2} \ge \zeta^{2} \ge \zeta^{2}(|\mathcal{R}\|\mathcal{H}|)^{-1}$. We have $112|\mathcal{R}\|\mathcal{H}| \le 120\log^{2}(\frac{nd}{\delta\zeta_{-}})$ provided that $n$ is a large enough constant. In light of (91), this implies that, for all $\tau$,

$$ \| [\Theta(\bar{P}_{\tau}, Q_{\text{cp}}^{\dagger\tau}) - \bar{\Theta}(\bar{P}_{\tau}, Q_{\text{cp}}^{\dagger\tau})]_{\sqrt{r^{\dagger\tau}h^{\dagger\tau}}} \|_{F}^{2} \ge \frac{1}{120 \log^{2}(\frac{nd}{\delta\zeta_{-}})} \| M(\bar{P}_{\tau}) - \bar{M}(\bar{P}_{\tau}) \|_{F}^{2} \quad (93) $$

$$ \ge \frac{1}{120 \log^2(\frac{nd}{\delta\zeta_{-}})} \| \Theta(\bar{P}_{\tau}, Q_{r^{\dagger\tau}}) - \bar{\Theta}(\bar{P}_{\tau}, Q_{r^{\dagger\tau}}) \|_{F}^{2}, \quad (94) $$

where we recall that $Q_{r^{\dagger\tau}}$ is the collection of all blocks at scale $r^{\dagger\tau}$ and we use the Pythagorean equality in the second line. Applying Lemma D.1 at the scale $r^{\dagger\tau} \in \mathcal{R}$, at the height $h^{\dagger\tau} \in \mathcal{H}$, and at all steps $\tau = 0, \dots, \tau_{\infty} - 1$, we deduce that the event $\bar{\xi}_{\text{cp}} := \bigcap_{\tau=0}^{\tau_{\infty}-1} \xi_{\text{cp}}(\bar{P}_{\tau}, h^{\dagger\tau}, r^{\dagger\tau})$ holds with probability at least $1 - \tau_{\infty}\delta$. Under this event, we write $\bar{Q}_{\text{cp}}^{\tau}$ for the estimated set defined at step $\tau$ and scales $(h^{\dagger\tau}, r^{\dagger\tau})$ in BlockSort. Then, it holds that $Q_{\text{cp}}^{\dagger\tau} \subset \bar{Q}_{\text{cp}}^{\tau} \subset \bar{Q}_{\text{cp}}^{\dagger\tau}$ and we deduce from (94) that

$$ \| [\Theta(\bar{P}_{\tau}, \bar{Q}_{\text{cp}}^{\tau}) - \bar{\Theta}(\bar{P}_{\tau}, \bar{Q}_{\text{cp}}^{\tau})]_{\sqrt{r^{\dagger\tau}h^{\dagger\tau}}} \|_{F}^{2} \ge \frac{1}{120 \log^{2}(\frac{nd}{\delta\tau_{-}})} \| \Theta(\bar{P}_{\tau}, Q_{r^{\dagger\tau}}) - \bar{\Theta}(\bar{P}_{\tau}, Q_{r^{\dagger\tau}}) \|_{F}^{2}. $$

Since (92) is not satisfied, we also have

$$ \begin{aligned} \| \Theta(\bar{P}_{\tau}, \bar{Q}_{\text{cp}}^{\tau}) - \bar{\Theta}(\bar{P}_{\tau}, \bar{Q}_{\text{cp}}^{\tau}) \|_{F}^{2} &\ge \| [\Theta(\bar{P}_{\tau}, \bar{Q}_{\text{cp}}^{\tau}) - \bar{\Theta}(\bar{P}_{\tau}, \bar{Q}_{\text{cp}}^{\tau})]_{\sqrt{r^{\dagger\tau}h^{\dagger\tau}}} \|_{F}^{2} \\ &\ge \| [\Theta(\bar{P}_{\tau}, Q_{\text{cp}}^{\dagger\tau}) - \bar{\Theta}(\bar{P}_{\tau}, Q_{\text{cp}}^{\dagger\tau})]_{\sqrt{r^{\dagger\tau}h^{\dagger\tau}}} \|_{F}^{2} \\ &\ge 4 \cdot 10^{5} \zeta^{2} \log^{3} \left( \frac{6nd}{\delta\zeta_{-}} \right) \Psi(|\bar{P}_{\tau}|, r^{\dagger\tau}, h^{\dagger\tau}, |\bar{Q}_{\text{cp}}^{\tau}|), \end{aligned} $$

since $\bar{Q}_{\text{cp}}^{\tau} \subset \bar{Q}_{\text{cp}}^{\dagger\tau}$. Hence, we are in position to apply Corollary D.6 at all steps $\tau$ with $r^{\dagger\tau}, \bar{P}_{\tau}, \bar{Q}_{\text{cp}}^{\tau}$, and $\eta = \sqrt{r^{\dagger\tau}h^{\dagger\tau}}$. There exists an event of probability higher than $1 - 4\tau_{\infty}\delta$ such that, at all steps $\tau$, we have

$$ \| \Theta(\bar{P}_{\tau+1}, Q_{r^{\dagger\tau}}) - \bar{\Theta}(\bar{P}_{\tau+1}, Q_{r^{\dagger\tau}}) \|_{F}^{2} \le \left( 1 - \frac{1}{3 \cdot 10^{5} \log^{4}(\frac{nd}{\delta\zeta_{-}})} \right) \| \Theta(\bar{P}_{\tau}; Q_{r^{\dagger\tau}}) - \bar{\Theta}(\bar{P}_{\tau}; Q_{r^{\dagger\tau}}) \|_{F}^{2}. $$

Together with Equation (93), we deduce that

$$ \begin{aligned} & \| M(\bar{P}_{\tau}) - \bar{M}(\bar{P}_{\tau}) \|_{F}^{2} - \| M(\bar{P}_{\tau+1}) - \bar{M}(\bar{P}_{\tau+1}) \|_{F}^{2} \\ & \ge \| \Theta(\bar{P}_{\tau}, Q_{r^{\dagger\tau}}) - \bar{\Theta}(\bar{P}_{\tau+1}, Q_{r^{\dagger\tau}}) \|_{F}^{2} - \| \Theta(\bar{P}_{\tau+1}, Q_{r^{\dagger\tau}}) - \bar{\Theta}(\bar{P}_{\tau}, Q_{r^{\dagger\tau}}) \|_{F}^{2} \\ & \ge \frac{1}{4 \cdot 10^{7} \log^{6}(\frac{nd}{\delta\zeta_{-}})} \| M(\bar{P}_{\tau}) - \bar{M}(\bar{P}_{\tau}) \|_{F}^{2}. \end{aligned} $$

Hence,

$$ \begin{aligned} \| M(\bar{P}_{\tau_0}) \|_{F}^{2} &\ge \| M(\bar{P}_{\tau_0}) - \bar{M}(\bar{P}_{\tau_0}) \|_{F}^{2} \\ &\ge \| M(\bar{P}_{\tau_{\infty}}) - \bar{M}(\bar{P}_{\tau_{\infty}}) \|_{F}^{2} \left( 1 - \frac{1}{4 \cdot 10^{7} \log^{6}(\frac{nd}{\delta\zeta_{-}})} \right)^{-\tau_{\infty}}. \end{aligned} $$

Since (92) does not hold at $\tau = \tau_{\infty}$, this implies that the Frobenius norm in the right-hand side of the above inequality is larger than $2\zeta^2$ and, in light of the definition of $\tau_{\infty} = 4 \cdot 10^7 \log^7(\frac{nd}{\delta(\zeta_-)^2})$, the right-hand side is larger than $2nd$. This contradicts the fact that $\|M(\bar{P}_{\tau_0})\|_F^2 \le nd$ since the entries of $M$ lie in $[0, 1]$.
Proof of Corollary D.8. To ease the notation in this proof, we simply write $P$ for $\overline{P}^{\dagger}$, $r$ for $r^{\dagger}$, $\overline{Q}_{cp}^{*}$ for $\overline{Q}_{cp}^{\dagger}$, and $h$ for $h^{\dagger}$. Since $\overline{Q}_{cp}^{*}$ corresponds to a set of blocks of questions of size $r$, it follows that $|\overline{Q}_{cp}^{*}| \le d/r$. This, in turn, implies that $\sqrt{rh}|P|\sqrt{|\overline{Q}_{cp}^{*}|} \le |P|h\sqrt{d}$ and $\sqrt{|P||\overline{Q}_{cp}^{*}|} \le \sqrt{|P|d}$. We have proven that

$$ \frac{\sqrt{rh}|P|\sqrt{|\overline{Q}_{cp}^{*}|}}{\zeta} \wedge (\sqrt{|P||\overline{Q}_{cp}^{*}|} + |P|) \le \frac{|G|h\sqrt{d}}{\zeta} \wedge (\sqrt{|G|d} + |G|) . \quad (95) $$

Second, we know from Lemma D.2 that $|\overline{Q}_{cp}^{*}| \le 64\frac{\tilde{r}}{rh}$ so that

$$ \frac{\sqrt{rh}|P|\sqrt{|\overline{Q}_{cp}^{*}|}}{\zeta} \wedge (\sqrt{|P||\overline{Q}_{cp}^{*}|} + |P|) \le \frac{|P|\sqrt{\tilde{r}h}}{\zeta} \wedge (\sqrt{|P|\frac{\tilde{r}}{rh}} + |P|) . \quad (96) $$

If $r > 32\zeta^2 \log(\frac{2d}{\delta}) \frac{1}{|P|h^2}$ then, it follows from the definition (53) of $\tilde{r}$ that $\tilde{r} = 8r$ so that the right-hand side of (96) is at most of the order of $\sqrt{|P|/h} + |P|$. For a smaller $r$, we know from (53) that $\tilde{r} \le \zeta^2 \log(\frac{2d}{\delta})/(|P|h^2)$, which in turn implies that

$$ \frac{|P|\sqrt{\tilde{r}h}}{\zeta} \le \sqrt{\log(\frac{2d}{\delta})} \sqrt{\frac{|P|}{h}} . $$

Hence, we deduce from (96) that

$$ \frac{\sqrt{rh}|P|\sqrt{|\overline{Q}_{cp}^{*}|}}{\zeta} \wedge (\sqrt{|P||\overline{Q}_{cp}^{*}|} + |P|) \le \sqrt{\log(\frac{2d}{\delta})} (\sqrt{\frac{|P|}{h}} + |P|) . $$

Together with (95), this leads us to

$$ \frac{\sqrt{rh}|P|\sqrt{|\overline{Q}_{cp}^{*}|}}{\zeta} \wedge (\sqrt{|P||\overline{Q}_{cp}^{*}|} + |P|) \le \sqrt{\log(\frac{2d}{\delta})} \left[ \frac{|G|h\sqrt{d}}{\zeta} \wedge |G|\sqrt{d} \wedge \sqrt{\frac{|G|}{h}} + |G| \right] , $$

which, together with (65) concludes the proof.

□

## Appendix F: Proof of Proposition B.6

In this section, we prove Proposition B.6 which states a tighter bound than Proposition B.5 on **TreeSort** when we use the variant **DimensionReduction-WM** to compute $\hat{\pi}_{WM}$. Recall that, for any $t = 1, \dots, t_{\infty}$, $T_t$ stands for the hierarchical sorting tree built by **TreeSort** at the beginning of step $t$. Thus, $T_t$ has depth $t$.

The main difference with the analysis of Proposition B.5 lies in the analysis of the algorithm **DimensionReduction-WM**, which is the purpose of the next subsection. Then, we combine it with the general scheme of the proof of Proposition B.6 to get the desired bound.

### F.1. Analysis of DimensionReduction-WM

The key idea of **DimensionReduction-WM** is to examine the high-variation regions of the observations not only in a set of experts $\overline{P}$ but also in the neighboring sets of experts. For this reason, we remind the reader of the notation of **DimensionReduction-WM**. Through
this subsection, we fix the step $t \ge 0$ of **TreeSort**. For simplicity, we write $\mathcal{T} := \mathcal{T}_t$. Recall that $\mathcal{L}^{(0,1)}(\mathcal{T})$ stands for the set of leaves of $\mathcal{T}$ of type **0** or **1**. By definition, those leaves are all at depth $t$. Let us focus on a specific leaf $G \in \mathcal{L}^{(0,1)}(\mathcal{T})$, and we consider a subset $\bar{P}$ of $G$.

Finally, we recall that we consider an ordering of the leaves $\mathcal{L}^{(0,1)}(\mathcal{T})$ at depth $t$ and centered on $G$ as:

$$ (G^{(a)})_{a \in \mathbb{Z}} = \mathbf{Order}(\mathcal{T}, G), $$

where $G^{(0)} = G$.

Also, we fix any $h \in \mathcal{H}$ and $r \in \mathcal{R}$. As in **DimensionReduction-WM**, define

$$ r_0 = 2^9 \log(4d|\mathcal{R}|/\delta) \frac{\zeta^2}{|\bar{P}|h^2} \quad \text{and} \quad \tilde{r} = 4([r_0]^{dya} \lor r), \qquad (97) $$

where $[r_0]^{dya} = 2^{\lceil \log_2(r_0) \rceil}$ is the smaller power of 2 which is larger than $r_0$. Up to numerical constants, $\tilde{r}$ is defined as for the original procedure **DimensionReduction**. If $r \ge r_0$, then we can simply rely on CUSUM statistics at the scale $8r$ and on the set $\bar{P}$ to detect high variation regions in $\bar{P}$. If $h$ (or $|\bar{P}|$) is so small that $r_0 > r$, we applied the CUSUM statistic at a larger scale $\tilde{r}$ in **DimensionReduction**. In this version, we compute the CUSUM statistics at a scale smaller than $\tilde{r}$ to the price of considering more experts than those in $\bar{P}$.

If $r < [r_0]^{dya}$, let us consider any $r_{cp} \in [8r, 2\tilde{r}] \cap \mathcal{R}$. We respectively define

$$ a_{WM}^{+} := a_{WM}^{+}(\mathcal{T}, G, h, r_{cp}) = \min \left\{ a : |G^{(1)}| + \dots + |G^{(a)}| \ge 2^{11} \log(4d|\mathcal{R}|/\delta) \frac{\zeta^2}{r_{cp}h^2} \right\}; $$

$$ a_{WM}^{-} := a_{WM}^{-}(\mathcal{T}, G, h, r_{cp}) = \min \left\{ a : |G^{(-1)}| + \dots + |G^{(-a)}| \ge 2^{11} \log(4d|\mathcal{R}|/\delta) \frac{\zeta^2}{r_{cp}h^2} \right\}, $$

as the minimum number of groups above and below $G$ in such a way that there are enough experts to detect a $h$-variation in the mean at the scale $r_{cp}$. Then, $\mathcal{V}_{r_{cp}}^{+}$ and $\mathcal{V}_{r_{cp}}^{-}$ stand for the collection of experts in the corresponding groups:

$$ \mathcal{V}_{r_{cp}}^{+} := \mathcal{V}_{r_{cp}}^{+}(\mathcal{T}, \bar{P}, h) = \bigcup_{a=1}^{a_{WM}^{+}} G^{(a)} \quad \text{and} \quad \mathcal{V}_{r_{cp}}^{-} := \mathcal{V}_{r_{cp}}^{-}(\mathcal{T}, \bar{P}, h) = \bigcup_{a=-a_{WM}^{-}}^{-1} G^{(a)}, \qquad (98) $$

Finally, we define

$$ \mathcal{V}_{r_{cp}} := \mathcal{V}_{r_{cp}}(\mathcal{T}, \bar{P}, h) = \begin{cases} \mathcal{V}_{r_{cp}}^{+} \cup \mathcal{V}_{r_{cp}}^{-} & \text{if } r_{cp} \le \tilde{r} \\ \bar{P} & \text{if } r_{cp} = 2\tilde{r} \end{cases} \qquad (99) $$

which exactly corresponds to the definition at Line 4 and Line 6 of **DimensionReduction-WM**. For any $k \in [d]$, we recall here the definition of the statistic $\hat{\mathbf{\Delta}}_{k,r_{cp}}^{(\text{ext})}$ its deterministic counterpart:

$$ \hat{\mathbf{\Delta}}_{k,r_{cp}}^{(\text{ext})} = \frac{1}{2r_{cp}} \sum_{k'=k-r_{cp}}^{k+r_{cp}-1} \bar{y}_{k'}(\mathcal{V}_{r_{cp}}^{+}) - \bar{y}_{k'}(\mathcal{V}_{r_{cp}}^{-}) \quad \text{and} \quad \mathbf{\Delta}_{k,r_{cp}}^{*(\text{ext})} = \frac{1}{2r_{cp}} \sum_{k'=k-r_{cp}}^{k+r_{cp}-1} \bar{m}_{k'}(\mathcal{V}_{r_{cp}}^{+}) - \bar{m}_{k'}(\mathcal{V}_{r_{cp}}^{-}). $$

In the notation of $\hat{\mathbf{\Delta}}_{k,r_{cp}}^{(\text{ext})}$, we remove the dependency on $\mathcal{V}_{r_{cp}}^{+}$ and $\mathcal{V}_{r_{cp}}^{-}$ to simplify the notation. Here, $\hat{\mathbf{\Delta}}_{k,r_{cp}}^{(\text{ext})}$ stands for the width between the empirical means of the groups above $\bar{P}$ and below $\bar{P}$. Recall also the definition of the statistic $\tilde{\mathbf{C}}_{k,2r_{cp}}^{(\text{ext})}$ and introduce its deterministic counterpart:

$$ \begin{aligned} \tilde{\mathbf{C}}_{k,2r_{cp}}^{(\text{ext})} &= \frac{1}{2r_{cp}} \left( \sum_{k'=k}^{k+2r_{cp}-1} \bar{y}_{k'}(\mathcal{V}_{2r_{cp}}) - \sum_{k'=k-2r_{cp}}^{k-1} \bar{y}_{k'}(\mathcal{V}_{2r_{cp}}) \right) \\ \tilde{\mathbf{C}}_{k,2r_{cp}}^{*(\text{ext})} &= \frac{1}{2r_{cp}} \left( \sum_{k'=k}^{k+2r_{cp}-1} \bar{m}_{k'}(\mathcal{V}_{2r_{cp}}) - \sum_{k'=k-2r_{cp}}^{k-1} \bar{m}_{k'}(\mathcal{V}_{2r_{cp}}) \right). \end{aligned} $$
Here, $\tilde{\mathbf{C}}_{k,2r_{cp}}^{(\text{ext})}$ stands for the mean CUSUM statistic over the experts in $\mathcal{V}_{2r_{cp}}$. Consider any $r_{cp} \in [4r, \tilde{r}] \cap \mathcal{R}$. Then, as in the algorithm **DimensionReduction-WM**, we define the collection of positions where both the width and the CUSUM statistic are large:

$$ \tilde{D}_{WM} := \tilde{D}_{WM}(\mathcal{T}, \bar{P}, h, r, r_{cp}) = \left\{ k : \Delta_{k,r_{cp}}^{(\text{ext})} \ge \frac{h}{16} \text{ and } \tilde{\mathbf{C}}_{k,2r_{cp}}^{(\text{ext})} \ge \frac{h}{16} \right\}. $$

See Figure 5 for illustrations. Then, we define $D_{WM}^*$ and $\tilde{D}_{WM}^*$ as the population counterparts of $\tilde{D}_{WM}$ with different constants

$$ D_{WM}^*(\mathcal{T}, \bar{P}, h, r, r_{cp}) = \left\{ k \in 1, \dots, d : \mathbf{C}_{k, 2r_{cp}}^{*(\text{ext})} \ge \frac{h}{8} \text{ and } \Delta_{k, r_{cp}}^{*(\text{ext})} \ge \frac{h}{8} \right\}; $$

$$ \tilde{D}_{WM}^*(\mathcal{T}, \bar{P}, h, r, r_{cp}) = \left\{ k \in 1, \dots, d : \mathbf{C}_{k, 2r_{cp}}^{*(\text{ext})} \ge \frac{h}{32} \text{ and } \Delta_{k, r_{cp}}^{*(\text{ext})} \ge \frac{h}{32} \right\}. $$

Then, we consider the collections of blocks $\tilde{Q}_{WM}(\mathcal{T}, \bar{P}, h, r, r_{cp})$, $Q_{WM}^*(\mathcal{T}, \bar{P}, h, r, r_{cp})$, and $\tilde{Q}_{WM}(\mathcal{T}, \bar{P}, h, r, r_{cp})$ of size $r$. With our notation, this means that $Q_{WM}^*(\mathcal{T}, \bar{P}, h, r, r_{cp}) = \text{Encode-Set}(D_{WM}^*, r)$, $\tilde{Q}_{WM}^*(\mathcal{T}, \bar{P}, h, r, r_{cp}) = \text{Encode-Set}(\tilde{D}_{WM}^*, r)$, and $\tilde{Q}_{WM}(\mathcal{T}, \bar{P}, h, r, r_{cp}) = \text{Encode-Set}(\tilde{D}_{WM}, r)$. Finally, we consider the unions over all possible $r_{cp} \in \mathcal{R}$ with $4r \le r_{cp} \le \tilde{r}$:

$$ \tilde{Q}_{WM} := \tilde{Q}_{WM}(\mathcal{T}, \bar{P}, h, r) = \bigcup_{r_{cp}=4r}^{\tilde{r}} \tilde{Q}_{WM}(\mathcal{T}, \bar{P}, h, r, r_{cp}) ; $$

$$ Q_{WM}^* := Q_{WM}^*(\mathcal{T}, \bar{P}, h, r) = \bigcup_{r_{cp}=4r}^{\tilde{r}} Q_{WM}^*(\mathcal{T}, \bar{P}, h, r, r_{cp}) ; $$

$$ \tilde{Q}_{WM}^* := \tilde{Q}_{WM}^*(\mathcal{T}, \bar{P}, h, r) = \bigcup_{r_{cp}=4r}^{\tilde{r}} \tilde{Q}_{WM}^*(\mathcal{T}, \bar{P}, h, r, r_{cp}) . $$

The following lemma states that, with high probability, $\tilde{Q}_{WM}$ is sandwiched between $Q_{WM}^*$ and $\tilde{Q}_{WM}^*$, so that, on the corresponding event, it is sufficient to study these two quantities.

**Lemma F.1.** Consider any valid hierarchical sorting tree $\mathcal{T}$, any subset $\bar{P}$ of a leaf $G$ of $\mathcal{T}$, any $h \in \mathcal{H}$, and any $r \in \mathcal{R}$. With probability at least $1 - \delta$, it holds that

$$ Q_{WM}^* \subset \tilde{Q}_{WM} \subset \tilde{Q}_{WM}^* . \qquad (100) $$

Next, we show that the aggregation of $M(\bar{P})$ at $Q_{WM}^*$ captures most of the variance of $M(\bar{P})$.

**Lemma F.2.** Assume that $\mathcal{T}$ is a valid hierarchical sorting tree. Then, there exist $h \in \mathcal{H}$ and $r \in \mathcal{R}$ such that

$$ \|M(\bar{P}) - \bar{M}(\bar{P})\|_F^2 \le 16\zeta^2 + 96|\mathcal{R}|\|\mathcal{H}\| \left\| [\Theta(\bar{P}, Q_{WM}^*) - \bar{\Theta}(\bar{P}, Q_{WM}^*)]_{\sqrt{\tilde{r}h}} \right\|_F^2 . \quad (101) $$

Recall that $\mathcal{T}_{t_\infty}$ (and in particular also $\mathcal{T} = \mathcal{T}_t$) is a valid hierarchical sorting tree under the event $\xi$ of high probability defined in Corollary B.4. This lemma is the counterpart of Lemma D.3 for the oblivious **DimensionReduction** algorithm.

## F.2. Analysis of the variant BlockSort with DoubleTrisection-WM

Recall the definition (64) of the function $\Psi$ by $\Psi(p, r, h, q) = \frac{hp\sqrt{rq}}{\zeta} \wedge \sqrt{pq} + p$. In Proposition D.7, we stated a high probability control for the result of **BlockSort** when fed with
**DimensionReduction.** In particular, this proposition only used the properties of **DimensionReduction** stated in Lemmas D.1 and D.3. As we have proven in Lemmas F.1 and F.2 (their counterparts for **DimensionReduction** – **WM**), we readily obtain the following result whose proof is omitted.

**Proposition F.3.** Assume that $\mathcal{T}_t$ is a valid hierarchical sorting tree. Consider a leaf $G$ of $\mathcal{T}$ of type **0** or **1** at depth $t$. With probability higher than $1 - 5\tau_\infty\delta$, there exists a subset $\bar{P}^\dagger$ such that $\bar{P} \subseteq \bar{P}^\dagger \subseteq G$ and the following property holds. For some $r_{cp}^\dagger \ge r^\dagger \in \mathcal{R}$ and some $h^\dagger \in \mathcal{H}$, upon writing $Q_{WM}^\dagger = Q_{WM}^*$ and $\bar{Q}_{WM}^\dagger = \bar{Q}_{WM}^*$, we have simultaneously

$$ \| [\Theta(\bar{P}^\dagger, Q_{WM}^\dagger) - \bar{\Theta}(\bar{P}^\dagger, Q_{WM}^\dagger)]_{\sqrt{r^\dagger h^\dagger}}^2 \|_F^2 \le 4 \cdot 10^5 \zeta^2 \log^3 \left( \frac{6nd}{\delta\zeta} \right) \Psi(|\bar{P}^\dagger|, r^\dagger, h^\dagger, |\bar{Q}_{WM}^\dagger|) ; \quad (102) $$

$$ \|M(\bar{P}^\dagger) - \bar{M}(\bar{P}^\dagger)\|_F^2 \le 16\zeta^2 + 96|\mathcal{R}\|\mathcal{H}\|\|[\Theta(\bar{P}^\dagger, Q_{WM}^\dagger) - \bar{\Theta}(\bar{P}^\dagger, Q_{WM}^\dagger)]_{\sqrt{r^\dagger h^\dagger}}\|_F^2 . \quad (103) $$

Since $\|M(\bar{P}) - \bar{M}(\bar{P})\|_F^2 \le \|M(\bar{P}^\dagger) - \bar{M}(\bar{P}^\dagger)\|_F^2$, the above proposition controls $\|M(\bar{P}) - \bar{M}(\bar{P})\|_F^2$ in terms of $\Psi(|\bar{P}^\dagger|, r^\dagger, h^\dagger, |\bar{Q}_{WM}^\dagger|)$.

### F.3. Analysis of the complete procedure TreeSort with DoubleTrisection - WM

In light of Proposition F.3, we need to control the cardinality of $|\bar{Q}_{WM}^\dagger|$. In comparison to the oblivious procedure analyzed in the previous section, the main improvement here is that the typical cardinalities $|\bar{Q}_{WM}^\dagger|$ are smaller than $|\bar{Q}_{cp}^\dagger|$ thanks to the refined dimension reduction procedure **DimensionReduction** – **WM**.

Unfortunately, it is not possible to get a tight control of the cardinality of each $\bar{Q}_{WM}^\dagger$ individually. Still, we are able to show that among all groups $G \in \mathcal{L}^{(0,1)}(\mathcal{T}_t)$ that are refined in the $t$-th iteration of **TreeSort**, many of them will correspond to small $|\bar{Q}_{WM}^\dagger|$. To formalize this argument, we need to be careful about the dependencies of the quantities under consideration.

We start from the ordered collection $\mathcal{L}^{(0,1)}(\mathcal{T}_t)$ of $v \le 2^t$ leaves of types **0** or **1**. We write $G_1, \dots, G_v$ for these groups and we are given a collection $\bar{P}_1, \dots, \bar{P}_v$ of subgroups such that $\bar{P}_i \subset G_i$ for $i = 1, \dots, v$. Later, we will specify $\bar{P}_v = \bar{P}_v^\dagger$, but those sets can be considered arbitrarily.

For a specific group $\bar{P}_v \subset G_v$, we write $\bar{Q}_{WM}^\dagger(\bar{P}_v, h, r)$ instead of $\bar{Q}_{WM}^\dagger$ to emphasize its dependency on $\bar{P}_v$, $r$ and $h$. Given a positive integer $p > 0$, we define $\mathcal{P}^*(p) = \{\bar{P}_v : |\bar{P}_v| \in [p, 2p)\}$ the collection of groups $\bar{P}_v$ of size in $[p, 2p)$.

**Lemma F.4.** Assume that $\mathcal{T}_t$ is a valid hierarchical sorting tree. For any $h \in \mathcal{H}$, $r \in \mathcal{R}$, any integer $p$, any sequence $\bar{P}_v$ of subsets of $G_v$, it holds that

$$ \sum_{\bar{P} \in \mathcal{P}^*(p)} |\bar{Q}_{WM}^*(\bar{P}, h, r)| \le \log(d) \left[ \frac{\sqrt{nd(r_0 \vee r)}}{rh\sqrt{p}} \wedge \frac{d(r_0 \vee r)}{r^2h} \wedge \frac{nd}{pr} \wedge \frac{n(r_0 \vee r)}{prh} \right] . \quad (104) $$

We are now equipped to prove Proposition B.6.

**Proof of Proposition B.6.** We work under the event $\xi$ (Corollary B.4) ensuring $\mathcal{T}_\infty$ and in particular $\mathcal{T}_t$ is a valid hierarchical sorting tree. For each group $G_s \in \mathcal{L}^{(0,1)}(\mathcal{T}_t)$ we apply Proposition F.3 and define a corresponding subgroup $\bar{P}^\dagger$, with $r^\dagger \in \mathcal{R}$, $h^\dagger \in \mathcal{H}$ and a corresponding collection of blocks $\bar{Q}_{WM}^\dagger$. Define the collection $\mathcal{D}_n = \{1, 2, 4, \dots, 2^{\lfloor \log_2(n) \rfloor}\}$. For $p \in \mathcal{D}_n$, we define $\mathcal{P}^*(p, h, r)$ as the collection of groups $\bar{P}^\dagger$ satisfying $|\bar{P}^\dagger| \in [p, 2p)$, $h^\dagger = h$, and $r^\dagger = r$.
Then, we derive from Proposition F.3 that, on an additional event of probability higher than $1 - 5 \cdot 2^t \tau_\infty \delta$, we have

$$ \sum_{\overline{P} \in \mathcal{L}_t} \|M(\overline{P}) - \overline{M}(\overline{P})\|_F^2 \\ \le 16\zeta^2 |\overline{\mathcal{L}}_t| + 96 |\mathcal{R}| \|\mathcal{H}\| \sum_{p,h,r} \sum_{\overline{P}^\dagger \in \mathcal{P}^*(p,h,r)} \left\| \left[ \Theta(\overline{P}^\dagger, \overline{Q}_{WM}^\dagger) - \overline{\Theta}(\overline{P}^\dagger, \overline{Q}_{WM}^\dagger) \right]_{\sqrt{rh}} \right\|_F^2 $$

$$ \stackrel{(a)}{\lesssim} \zeta^2 \log^5 \left( \frac{6nd}{\delta\zeta_-} \right) \sum_{p,h,r} \sum_{\overline{P}^\dagger \in \mathcal{P}^*(p,h,r)} \left[ \sqrt{[\frac{h^2pr}{\zeta^2} \wedge 1] p |\overline{Q}_{WM}^*(\overline{P}^\dagger, h, r)| + p} \right] $$

$$ \stackrel{(b)}{\lesssim} \zeta^2 \log^{5.5} \left( \frac{6nd}{\delta\zeta_-} \right) \sum_{p,h,r} \left[ \sqrt{\frac{r}{r \vee r_0} p |\mathcal{P}^*(p, h, r)| \sum_{\overline{P}^\dagger \in \mathcal{P}^*(p, h, r)} |\overline{Q}_{WM}^*(\overline{P}^\dagger, h, r)| + p |\mathcal{P}^*(p, h, r)|} \right] $$

$$ \stackrel{(c)}{\lesssim} \zeta^2 \log^{5.5} \left( \frac{6nd}{\delta\zeta_-} \right) \sum_{p,h,r} \left[ \sqrt{\frac{nr}{r \vee r_0} \sum_{\overline{P}^\dagger \in \mathcal{P}^*(p,h,r)} |\overline{Q}_{WM}^*(\overline{P}^\dagger, h, r)| + n} \right] $$

$$ \stackrel{(d)}{\lesssim} \zeta^2 \log^6 \left( \frac{6nd}{\delta\zeta_-} \right) \sum_{p,h,r} \left[ \left( n^{3/4} d^{1/4} \left( \frac{1}{(r_0 \vee r)ph^2} \right)^{1/4} \wedge n \sqrt{\frac{d}{p(r_0 \vee r)}} \wedge \frac{n}{\sqrt{ph}} \wedge \sqrt{\frac{nd}{rh}} \right) + n \right] $$

$$ \stackrel{(e)}{\lesssim} \zeta^2 \log^7 \left( \frac{6nd}{\delta\zeta_-} \right) \sum_{p,h} \left[ \left( \frac{n^{3/4} d^{1/4}}{\zeta^{1/2}} \wedge n \sqrt{d} \wedge \frac{nh}{\zeta} \sqrt{d} \wedge \frac{n}{\sqrt{h}} \wedge \frac{\sqrt{nd}}{\sqrt{h}} \right) + n \right] $$

$$ \stackrel{(e)}{\lesssim} \zeta^2 \log^7 \left( \frac{6nd}{\delta\zeta_-} \right) \sum_{p,h} \left[ \left( \frac{n^{3/4} d^{1/4}}{\zeta^{1/2}} \wedge n \sqrt{d} \wedge \frac{n^{2/3} \sqrt{d}}{\zeta^{1/3}} \wedge \frac{nd^{1/6}}{\zeta^{1/3}} \right) + n \right] $$

$$ \stackrel{(e)}{\lesssim} \zeta^2 \log^9 \left( \frac{6nd}{\delta\zeta_-} \right) \left[ \left( \frac{n^{3/4} d^{1/4}}{\zeta^{1/2}} \wedge n \sqrt{d} \wedge \frac{n^{2/3} \sqrt{d}}{\zeta^{1/3}} \wedge \frac{nd^{1/6}}{\zeta^{1/3}} \right) + n \right], $$

where we applied Proposition F.3 in (a), Jensen inequality and the definition of $r_0$ in (b), as well as the bound $|\mathcal{P}^*(p, h, r)| \le n/p$ in (c), Lemma F.4 in (d), and $x \wedge y \le x^{1/3}y^{2/3}$ in (e). $\square$

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

### F.4. Remaining proofs

*Proof of lemma F.1.* It is sufficient to prove that with high probability, $D_{WM}^*(T, P, h, r_{cp}) \subset \tilde{D}_{WM}(T, P, h, r_{cp}) \subset \overline{D}_{WM}^*(T, P, h, r_{cp})$ for all $r_{cp} \in [4r, \tilde{r}) \cap \mathcal{R}$. Recall that we use the convention that $\bar{y}_i = \bar{m}_i = 0$ if $i \le 0$ and $\bar{y}_i = \bar{m}_i = 1$ if $i > d$. Since the CUSUM and the envelope statistics are linear, we have the decompositions

$$ \begin{aligned} \tilde{\mathbf{C}}_{k,2r_{cp}}^{(\text{ext})}(\mathcal{V}_{2r_{cp}}) &= \mathbf{C}_{k,2r_{cp}}^{*(\text{ext})}(\mathcal{V}_{2r_{cp}}) + \frac{1}{2r_{cp}} \left( \sum_{k'=k}^{k+2r_{cp}-1} \bar{e}_{k'}(\mathcal{V}_{2r_{cp}}) - \sum_{k'=k-2r_{cp}}^{k-1} \bar{e}_{k'}(\mathcal{V}_{2r_{cp}}) \right) \\ \tilde{\mathbf{\Delta}}_{k,r_{cp}}^{(\text{ext})}(\mathcal{V}_{r_{cp}}^{+}, \mathcal{V}_{r_{cp}}^{-}) &= \mathbf{\Delta}_{k,r_{cp}}^{*(\text{ext})}(\mathcal{V}_{r_{cp}}^{+}, \mathcal{V}_{r_{cp}}^{-}) + \frac{1}{2r_{cp}} \sum_{k'=k-r_{cp}}^{k+r_{cp}-1} (\bar{e}_{k'}(\mathcal{V}_{r_{cp}}^{+}) - \bar{e}_{k'}(\mathcal{V}_{r_{cp}}^{-})) , \end{aligned} $$

where the two latter random variables are centered and respectively $\zeta(r_{cp}|\mathcal{V}_{2r_{cp}}|)^{-1/2}$-subGaussian and $\zeta[r_{cp}(|\mathcal{V}_{r_{cp}}^{+}|\wedge|\mathcal{V}_{r_{cp}}^{-}|)]^{-1/2}$-subGaussian. By a union bound, we deduce that, with probability
higher than 1 − δ, we have simultaneously

$$
\max_{r_{cp} \in [4r, \tilde{r}] \cap \mathcal{R}} \max_{k \in [d]} |\hat{\mathbf{C}}_{k, 2r_{cp}}^{*(\text{ext})} - \mathbf{C}_{k, 2r_{cp}}^{*(\text{ext})}| \le \zeta \sqrt{\frac{2}{r_{cp}} \frac{|\mathcal{V}_{2r_{cp}}|}{|\mathcal{V}_{r_{cp}}|} \log\left(\frac{4d|\mathcal{R}|}{\delta}\right)}; \quad (105)
$$

$$
\max_{r_{cp} \in [4r, \tilde{r}] \cap \mathcal{R}} \max_{k \in [d]} |\hat{\Delta}_{k, r_{cp}}^{*(\text{ext})} - \Delta_{k, r_{cp}}^{*(\text{ext})}| \le \zeta \sqrt{\frac{2}{(|V_{r_{cp}}^{+}| \wedge |V_{r_{cp}}^{-}|)r_{cp}} \log\left(\frac{4d|\mathcal{R}|}{\delta}\right)}. \quad (106)
$$

To conclude, it suffices to check that |V<sub>rcp</sub><sup>+</sup>|, |V<sub>rcp</sub><sup>-</sup>|, and |V<sub>rcp</sub>| have been chosen large enough so
that the right-hand side of the two above equations is at most h/32.

By definition of $\mathcal{V}_{rcp}^{+}$ and $\mathcal{V}_{rcp}^{-}$, we know that $|\mathcal{V}_{rcp}^{+}| \wedge |\mathcal{V}_{rcp}^{-}| \ge 2^{11} \log(4d|\mathcal{R}|/\delta) \frac{\zeta^2}{r_{cp}h^2}$ which implies that (106) is at most $h/32$.

If $r_{cp} \le \tilde{r}/2$, then $\mathcal{V}_{2r_{cp}} = |\mathcal{V}_{2r_{cp}}^{+}| + |\mathcal{V}_{2r_{cp}}^{-}| \ge 2^{11} \log(4d|\mathcal{R}|/\delta) \frac{\zeta^2}{r_{cp}h^2}$, which implies that (105) is at most $h/32$. Finally, for $r_{cp} = \tilde{r}$, we use

$$
r_{cp} \ge 4r_0 \ge 2^{11} \log(4d|\mathcal{R}|/\delta) \frac{\zeta^2}{|P|h^2}
$$

and that |V| = |P| to conclude that (105) is at most h/32.

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

Proof of Lemma F.2. In the analysis of **DimensionReduction**, we introduced in (55) the sets $D_{cp}^*(P, h, r)$ of questions such that the corresponding CUSUM of the mean expert in $P$ is above $h/2$ at scale $8r$. Recall the set $Q_{cp}^* := Q_{cp}^*(P, h, r) = \text{Encode} - \text{Set}(D_{cp}^*(P, h, r), r)$. In Lemma D.3, we stated that, for some $h \in \mathcal{H}$ and $r \in \mathcal{R}$, we have

$$
\| M(P) - \bar{M}(P) \|_{F}^{2} \leq 16\zeta^{2} + 96|\mathcal{R}|\|\mathcal{H}\| \left\| \left[ \Theta(P, Q_{\text{cp}}^{*}) - \bar{\Theta}(P, Q_{\text{cp}}^{*}) \right]_{\sqrt{rh}} \right\|_{F}^{2} . \quad (107)
$$

Define $D_{\text{env}}^* := D_{\text{env}}^*(T, P, h, r) = \{k \in [d] : \Delta_{k,r}^{*(\text{ext})}(V_r^+, V_r^-) \ge h/2\}$ for the questions where the population width between $V_r^+$ and $V_r^-$ at scale $r$ is at least $h/2$. Besides, we define $Q_{\text{env}}^* := Q_{\text{env}}^*(T, P, h, r) = \text{Encode} - \text{Set}(D_{\text{env}}^*, r)$. If $l \in Q_{\text{cp}}^* \setminus Q_{\text{env}}^*$, then for any $i, j \in P$, we have

$$
|\Theta_{i,l} - \Theta_{j,l}| \le \frac{1}{\sqrt{r}} \sum_{k'=lr}^{(l+1)r-1} \overline{m}_{k'}(V_r^+) - \overline{m}_{k'}(V_r^-) \le 2\sqrt{r}\Delta_{lr,r}^{*(\text{ext})} < \sqrt{rh}.
$$

Hence, it follows that

$$
\left\| \left[ \Theta(P, Q_{\text{cp}}^* - \bar{\Theta}(P, Q_{\text{cp}}^*) \right]_{\sqrt{rh}} \right\|_F^2 = \left\| \left[ \Theta(P, Q_{\text{cp}}^* \cap Q_{\text{env}}^* - \bar{\Theta}(P, Q_{\text{cp}}^* \cap Q_{\text{env}}^*) \right]_{\sqrt{rh}} \right\|_F^2 . \quad (108)
$$

In light of (107) and (108), we only have to prove that, for any fixed $\mathcal{T}$, $P$, $h$, and $r$, we have

$$
D_{\text{cp}}^{*}(P, h, r) \cap D_{\text{env}}^{*}(\mathcal{T}, P, h, r) \subset \bigcup_{r_{\text{cp}} \in [4r, \tilde{r}] \cap \mathcal{R}} D_{\text{WM}}^{*}(\mathcal{T}, P, h, r, r_{\text{cp}}) . \quad (109)
$$

Since the remainder of the proof heavily relies on the comparisons between CUSUM statistics
for different subsets of experts, we respectively write $\mathbf{C}_{k,r}^{*(\text{ext})}(\mathcal{V}_r)$ and $\mathbf{\Delta}_{k,r}^{*(\text{ext})}(\mathcal{V}_r^+, \mathcal{V}_r^-)$ instead of
$\mathbf{C}_{k,r}^{*(\text{ext})}$ and $\mathbf{\Delta}_{k,r}^{*(\text{ext})}$ to better keep track of the dependencies. Fix any question $k \in D_{\text{cp}}^*(P, h, r) \cap D_{\text{env}}^*(\mathcal{T}, P, h, r)$ and define

$$
r_{\min} = \max\{r' \in \mathcal{R} : \mathbf{C}_{k,r'}^{*(\text{ext})}(\mathcal{V}_{r'}) < h/8\},
$$

with the convention that max(Ø) = 1. $r_{\min}$ can be interpreted as the largest scale $r'$ in $\mathcal{R}$ such that the population CUSUM at scale $r'$ applied to $\mathcal{V}_{r'}$ is smaller than $h/8$. By definition, we
have $V_{2\tilde{r}} = P$. As a consequence, for any $r' \ge 2\tilde{r}$, we have $C_{k,r'}^{*(\text{ext})}(V_{r'}) = C_{k,r'}^{*}(P) \ge C_{k,2\tilde{r}}^{*}(P) \ge C_{k,8r}^{*}(P) \ge h/8$ since $k \in D_{\text{cp}}^{*}(P, h, r)$ and since $\tilde{r} \ge 8r$ (see (97)). This implies that $r_{\min} \le \tilde{r}$. We consider two distinct cases.

**Case 1:** $r_{\min} \le 4r$. Then, we simply choose $r_{\text{cp}} = 4r$. By definition of $r_{\min}$, we have $C_{k,2r_{\text{cp}}}^{*(\text{ext})}(V_{2r_{\text{cp}}}) \ge h/8$. Since $k \in D_{\text{env}}^{*}(T, P, h, r)$, we can lower bound the envelope statistic as

$$ \Delta_{k,r_{\text{cp}}}^{*(\text{ext})}(V_{r_{\text{cp}}}^{+}, V_{r_{\text{cp}}}^{-}) \ge \frac{1}{4} \Delta_{k,r}^{*(\text{ext})}(V_{r}^{+}, V_{r}^{-}) \ge h/8 . $$

We have proved that $k \in D_{WM}^{*}(T, P, h, r, r_{\text{cp}})$.

**Case 2:** $r_{\min} \in (4r, \tilde{r}]$. In that case, we choose $r_{\text{cp}} = r_{\min} \ge 8r$ (since $r_{\min}$ is a power of 2). By definition of $r_{\min}$, we have both $C_{k,2r_{\text{cp}}}^{*(\text{ext})} \ge h/8$ and $C_{k,r_{\text{cp}}}^{*(\text{ext})} < h/8$. Since $k \in D_{\text{cp}}^{*}(P, h, r)$ and $r_{\text{cp}} \ge 8r$, we also deduce by monotonicity that the CUSUM of the mean expert in P at scale $r_{\text{cp}}$ is higher than $h/2$, this is $C_{k,r_{\text{cp}}}^{*} \ge C_{k,8r}^{*} \ge h/2$ since $k \in D_{\text{cp}}^{*}(P, h, r)$ – see (55).

Remark that, since $r_{\text{cp}} \le \tilde{r}$, we have $V_{r_{\text{cp}}} = V_{r_{\text{cp}}}^{+} \cup V_{r_{\text{cp}}}^{-}$. Without loss of generality, we can assume that $|V_{r_{\text{cp}}}^{+}| \ge |V_{r_{\text{cp}}}^{-}|$. This implies in particular that

$$ \begin{aligned} r_{\text{cp}} C_{k,r_{\text{cp}}}^{*(\text{ext})}(V_{r_{\text{cp}}}) &\ge \frac{|V_{r_{\text{cp}}}^{+}|}{|V_{r_{\text{cp}}}|} \sum_{k'=k}^{k+r_{\text{cp}}-1} \overline{m}_k(V^{+}) - \frac{|V_{r_{\text{cp}}}^{+}|}{|V_{r_{\text{cp}}}|} \sum_{k'=k-r_{\text{cp}}}^{k-1} \overline{m}_k(V^{+}) \\ &\ge \frac{1}{2} \left( \sum_{k'=k}^{k+r_{\text{cp}}-1} \overline{m}_k(V_{r_{\text{cp}}}^{+}) - \sum_{k'=k-r_{\text{cp}}}^{k-1} \overline{m}_k(V_{r_{\text{cp}}}^{+}) \right). \end{aligned} $$

Since $C_{k,r_{\text{cp}}}^{*}(P) \ge h/2$ and $C_{k,r_{\text{cp}}}^{*(\text{ext})}(V_{r_{\text{cp}}}) \le h/8$, this implies that

$$ \begin{aligned} h/4 \le C_{k,r_{\text{cp}}}^{*}(P) - 2C_{k,r_{\text{cp}}}^{*(\text{ext})}(V_{r_{\text{cp}}}) &\le \frac{1}{r_{\text{cp}}} \left( \sum_{k'=k}^{k+r_{\text{cp}}-1} \overline{m}_{k'}(P) - \overline{m}_{k'}(V_{r_{\text{cp}}}^{+}) \right) + \frac{1}{r_{\text{cp}}} \left( \sum_{k'=k-r_{\text{cp}}}^{k-1} \overline{m}_{k'}(V_{r_{\text{cp}}}^{+}) - \overline{m}_{k'}(P) \right) \\ &\le \frac{1}{r_{\text{cp}}} \left( \sum_{k'=k-r_{\text{cp}}}^{k-1} \overline{m}_{k'}(V_{r_{\text{cp}}}^{+}) - \overline{m}_{k'}(P) \right) \\ &\le \frac{1}{r_{\text{cp}}} \left( \sum_{k'=k-r_{\text{cp}}}^{k+r_{\text{cp}}-1} \overline{m}_{k'}(V_{r_{\text{cp}}}^{+}) - \overline{m}_{k'}(V_{r_{\text{cp}}}^{-}) \right) \\ &= 2\Delta_{k,r_{\text{cp}}}^{*(\text{ext})}(V_{r_{\text{cp}}}^{+}, V_{r_{\text{cp}}}^{-}) . \end{aligned} $$

Hence, we have proved that $\Delta_{k,r_{\text{cp}}}^{*(\text{ext})}(V_{r_{\text{cp}}}^{+}, V_{r_{\text{cp}}}^{-}) \ge h/8$ and $C_{k,2r_{\text{cp}}}^{*(\text{ext})}(V_{r_{\text{cp}}}) \ge h/8$. Thus, $k \in D_{WM}(T, P, h, r, r_{\text{cp}})$. We have shown (109) and the proof is finished.

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

*Proof of Lemma F.4.* We fix $h \in \mathcal{H}$ and $r \in \mathcal{R}$. Let us consider a subgroup $\bar{P} \subset G \in \mathcal{L}^{(0,1)}(\mathcal{T})$ Recall that the blocks $\bar{Q}_{WM}(\bar{P}, h, r) = \cup_{r_{\text{cp}}=4r}^{\tilde{r}} \bar{Q}_{WM}(\bar{P}, h, r, r_{\text{cp}})$ – see the definitions in Section F.1. Again, we remove the dependency on $\mathcal{T}$ in $Q_{WM}^{*}(\bar{P}, h, r, r_{\text{cp}})$ for the ease of exposition. First, we bound $\sum_{\bar{P} \in \mathcal{P}^{*}(p)} |\bar{Q}_{WM}^{*}(\bar{P}, h, r, r_{\text{cp}})|$ before summing over the range over all possible $r_{\text{cp}}$.

Let us consider some $l \in \bar{Q}_{WM}^{*}(\bar{P}, h, r, r_{\text{cp}})$. By definition, there exists at least one question $k(l) \in [lr, (l+1)r)$ such that we have simultaneously $C_{k(l),2r_{\text{cp}}}^{*(\text{ext})} \ge h/32$ and $\bar{\Delta}_{k(l),r_{\text{cp}}}^{*(\text{ext})} \ge h/32$. For
$l \in Q_r \setminus \overline{Q}_{WM}^*(r_{cp})$, we simply define $k(l) = l$. We deduce from this definition that

$$|\overline{Q}_{WM}^*(\overline{P}, h, r, r_{cp})| \le \sum_{l \in Q_r} \mathbf{1}\{\overline{\mathbf{C}}_{k(l), 2r_{cp}}^{*(\text{ext})} \ge h/32\} \mathbf{1}\{\overline{\mathbf{\Delta}}_{k(l), r_{cp}}^{*(\text{ext})} \ge h/32\} . \quad (110)$$

This implies that

$$|\overline{Q}_{WM}^*(\overline{P}, h, r, r_{cp})| \le \frac{32}{h} \sum_{l \in Q_r} \overline{\mathbf{C}}_{k(l), 2r_{cp}}^{*(\text{ext})} \le 2^8 \frac{r_{cp}}{rh} \quad (111)$$

where the last inequality comes from the fact that the total variation of $\overline{m}(V_{2r_{cp}})$ is at most 1 and that, for any $l \in Q_r$, the interval $[k(l) - 2r_{cp}, k(l) + 2r_{cp})$ intersects at most $8r_{cp}/r$ intervals of the form $[k(l') - 2r_{cp}, k(l') + 2r_{cp})$ with $l' \in Q_r$.

Let $p$ be an integer and assume that $|\overline{P}| \in [p, 2p)$. Let us introduce $\Gamma := \Gamma(p, h, r_{cp}) = \frac{\tilde{r}}{r_{cp}} \ge 1$, where we recall that $\tilde{r} \ge 4r_0$ is defined by $r_0 = 2^9 \log(4d|\mathcal{R}|/\delta) \frac{\zeta^2}{ph^2}$ in (97). Intuitively, $\Gamma$ would correspond to the number $a_{WM}^+$ and $a_{WM}^-$ of sets of experts above $\overline{P}$ or below $\overline{P}$ that would be considered if those sets were of size $p$. More generally, $V_{r_{cp}}^+(\mathcal{T}, \overline{P}, h) = \cup_{a=1}^{a_{WM}^+} G^{(a)}$ contains at most $\Gamma$ groups of size at least $p$ among $G^{(1)}, \dots, G^{(a_{WM}^+ - 1)}$ since the total size of the groups $G^{(a)}$ with $a \le a_{WM}^+ - 1$ must be less than $2^{11} \log(4d|\mathcal{R}|/\delta) \frac{\zeta^2}{r_{cp}h^2}$. Thus, we deduce that $V_{r_{cp}}^-(\mathcal{T}, \overline{P}, h) \cup \overline{P} \cup V_{r_{cp}}^+(\mathcal{T}, \overline{P}, h)$ contains at most $2\Gamma + 3$ groups of size at least $p$.

The following lemma states that the neighbourhoods $V_{r_{cp}}^-(\mathcal{T}, \overline{P}, h) \cup \overline{P} \cup V_{r_{cp}}^+(\mathcal{T}, \overline{P}, h)$ of groups $\overline{P}$ in $\mathcal{P}^*(p)$ only intersect on a few groups.

**Lemma F.5.** Consider any group $\overline{P} \in \mathcal{P}^*(p)$. There exists at most $4\Gamma + 3$ groups $\overline{P}' \in \mathcal{P}^*(p)$ such that

$$(V_{r_{cp}}^-(\mathcal{T}, \overline{P}, h) \cup \overline{P} \cup V_{r_{cp}}^+(\mathcal{T}, \overline{P}, h)) \cap (V_{r_{cp}}^-(\mathcal{T}, \overline{P}', h) \cup \overline{P}' \cup V_{r_{cp}}^+(\mathcal{T}, \overline{P}', h)) \neq \emptyset . \quad (112)$$

As in the proof of Lemma D.9, we introduce the width of the matrix $M$ on a set $A$ of experts and an interval of questions $[k_1, k_2]$ by

$$W_{\infty, 1}(M, A, [k_1, k_2]) := \max_{i, j \in A} \sum_{k=k_1}^{k_2} |M_{i,k} - M_{j,k}| .$$

From (110) again, we deduce that

$$\begin{align*}
\sum_{\overline{P} \in \mathcal{P}^*(p)} |\overline{Q}_{WM}^*(\overline{P}, h, r, r_{cp})| &\le \frac{32}{h} \sum_{\overline{P} \in \mathcal{P}^*(p)} \sum_{l \in Q_r} \overline{\mathbf{\Delta}}_{k(l), r_{cp}}^{*(\text{ext})} (V_{r_{cp}}^+(\mathcal{T}, \overline{P}, h), V_{r_{cp}}^-(\mathcal{T}, \overline{P}, h)) \\
&\le \frac{32}{h} \sum_{l \in Q_r} \sum_{\overline{P} \in \mathcal{P}^*(p)} \frac{1}{2r_{cp}} W_{\infty, 1}(V_{r_{cp}}^+(\mathcal{T}, \overline{P}, h) \cup \overline{P} \cup V_{r_{cp}}^-(\mathcal{T}, \overline{P}, h), [k - r_{cp}, k + r_{cp}]) \\
&\le \frac{32}{rh}(4\Gamma + 3)d,
\end{align*}$$

where the last inequality comes Lemma F.5 and the fact that the sum over disjoints sets $V_{r_{cp}}^-(\overline{P}) \cup \overline{P} \cup V_{r_{cp}}^+(\overline{P})$ of $W_{\infty, 1}(V_{r_{cp}}^+(\overline{P}) \cup \overline{P} \cup V_{r_{cp}}^-(\overline{P}), [k - r_{cp}, k + r_{cp}])$ is upper bounded by $2r_{cp}$ since the total variation of any column of $M$ is at most 1.

Combining (111) with the latter upper bound together with $|\mathcal{P}^*(p)| \le n/p$ we deduce that

$$\sum_{\overline{P} \in \mathcal{P}^*(p)} |\overline{Q}_{WM}^*(\overline{P}, h, r, r_{cp})| \lesssim \frac{nr_{cp}}{prh} \wedge \frac{\Gamma d}{rh} . \quad (113)$$
If $r_0 > r$, then we have $\Gamma \le \frac{8r_0}{r_{cp}}$. This implies that

$$ \sum_{\bar{P} \in \mathcal{P}^*(p)} |\bar{Q}_{WM}^*(\bar{P}, h, r, r_{cp})| \le \frac{nr_{cp}}{prh} \wedge \frac{r_0 d}{r_{cp}rh} \le \frac{\sqrt{ndr_0}}{rh\sqrt{p}} . $$

Since $r_{cp} \le [4r, \tilde{r}] \cap \mathcal{R}$, there are at most $c \log(d)$ possible values for $r_{cp}$, we conclude that

$$ \sum_{r_{cp}} \sum_{\bar{P} \in \mathcal{P}^*(p)} |\bar{Q}_{WM}^*(\bar{P}, h, r, r_{cp})| \le \frac{nr_0}{prh} \wedge \frac{r_0 d}{r^2 h} \wedge \frac{\sqrt{ndr_0}}{rh\sqrt{p}} . $$

Otherwise, if $r_0 \le r$, then $\Gamma \le 8$ and $r_{cp} \in [4r, 8r]$. We deduce from (113) that

$$ \sum_{\bar{P} \in \mathcal{P}^*(p)} |\bar{Q}_{WM}^*(\bar{P}, h, r, r_{cp})| \le \frac{n}{ph} \wedge \frac{d}{rh} \le \frac{\sqrt{nd}}{\sqrt{rh}\sqrt{p}} . $$

We have proved that, in any case,

$$ \sum_{r_{cp}} \sum_{\bar{P} \in \mathcal{P}^*(p)} |\bar{Q}_{WM}^*(\bar{P}, h, r, r_{cp})| \le \log(d) \left[ \frac{d(r_0 \vee r)}{r^2 h} \wedge \frac{\sqrt{nd(r_0 \vee r)}}{rh\sqrt{p}} \right] . \quad (114) $$

To establish the remaining bound for the sum of $|\bar{Q}_{WM}^*(\bar{P}, h, r, r_{cp})|$, we control each $|\bar{Q}_{WM}^*(\bar{P}, h, r, r_{cp})|$ individually in a similar fashion to what we did for the analysis of the oblivious hierarchical sorting estimator $\hat{\pi}_{HT}$. First, we have $\bar{Q}_{WM}^*(\bar{P}, h, r, r_{cp}) \subset Q_r$ so that $|\bar{Q}_{WM}^*(\bar{P}, h, r, r_{cp})| \le d/r$. Besides, arguing as in the proof of Lemma D.2, $|\bar{Q}_{WM}^*(\bar{P}, h, r, r_{cp})| \le r_{cp}/(rh) \le (r_0 \vee r)/(rh)$.

$$ \sum_{r_{cp}} \sum_{\bar{P} \in \mathcal{P}^*(p)} |\bar{Q}_{WM}^*(\bar{P}, h, r, r_{cp})| \le \log(d) \left[ \frac{nd}{pr} \wedge \frac{n(r_0 \vee r)}{prh} \right] . \quad (115) $$

Combining (114) and (115) concludes the proof. $\square$

*Proof of Lemma F.5.* Consider two distinct groups $\bar{P}$ and $\bar{P}'$ in $\mathcal{P}^*(p)$. Let $(G^{(a)}(\bar{P}))_{a \in \mathbb{Z}} = \text{Order}(\mathcal{T}, \bar{P})$ be the ordering of $\mathcal{L}^{(0,1)}(\mathcal{T})$ centered on $\bar{P}$ and $a' \in \mathbb{Z}$ the index of the leaf $G^{(a')}(\bar{P})$ containing $\bar{P}'$. Obviously, $|G^{(a')}| \ge |\bar{P}'| \ge p$.

Without loss of generality, we assume that $a' > 0$. In that case, if (112) is satisfied then necessarily

$$ (\mathcal{V}_{r_{cp}}^{+}(\mathcal{T}, \bar{P}, h) \cup \bar{P}) \cap \mathcal{V}_{r_{cp}}^{-}(\mathcal{T}, \bar{P}', h) \neq \emptyset . $$

This can only happen if the number of leaves $G^{(a)}(\bar{P})$ for $0 < a < a'$ that are of size at least $p$ is less than or equal to $2\Gamma$. The same holds if $a' < 0$ and this proves the lemma. $\square$

# Appendix G: Proof of Lemma 4.2 and Theorem 4.3

## G.1. Proof of Lemma 4.2

We start with the case $\lambda_- \in [2/d, 1]$. The random variable $n_{i,[(j-1)l(\lambda)+1,jl(\lambda)]}$ is distributed as a Poisson random variable with parameter $\lambda l(\lambda)$. Let us apply Chernoff's inequality for Poisson random variable (e.g. [3], section 2.2). We have

$$ \mathbb{P}[n_{i,[(j-1)l(\lambda)+1,jl(\lambda)]} \le \lambda l(\lambda)/2] \le \exp\left[-\frac{3}{28}\lambda l(\lambda)\right] \le \frac{\delta}{nd}, $$
provided that $\lambda l(\lambda) \ge \frac{28}{3} \log(\text{nd}/\delta)$. Since $\lambda_- \le 1$, we have $\lambda l(\lambda)/2 \ge \Upsilon^*$. In view of the definition of $\Upsilon^*$, the condition $\lambda l(\lambda) \ge \frac{28}{3} \log(\text{nd}/\delta)$ is therefore valid and we conclude that

$$ \mathbb{P}[n_{i,[(j-1)l(\lambda)+1,jl(\lambda)]} \le \Upsilon^*] \le \frac{\delta}{nd}, $$

and the first result follows. Turning to the second result, we observe that $n_{i,\{j\}}$ is distributed as a Poisson random variable. We apply again Chernoff's inequality to derive that

$$ \mathbb{P}[n_{i,\{j\}} \le \frac{\lambda}{2}] \le \exp[-\frac{3}{28}\lambda] \le \frac{\delta}{nd}, $$

since $\lambda \ge \frac{28}{3} \log(\text{nd}/\delta)$. Since $\lambda \ge 2\lambda_-\Upsilon^*$, the result follows.

## G.2. Proof of Theorem 4.3

If $\lambda_- \le 2/d$, we use the trivial bound $\|M_{\hat{\pi}_{WMP}^{-1}} - M_{\pi^{*-1}}\|_F^2 \le nd$, which ensures that

$$ \mathbb{E}[\|M_{\hat{\pi}_{WMP}^{-1}} - M_{\pi^{*-1}}\|_F^2] \le \frac{n}{\lambda_-} \le c \log^{c'} \left( \frac{nd\lambda^{1/2}}{\zeta_-} \right) \frac{n}{\lambda}. $$

If $\lambda_- \ge 1$, then Lemma 4.2 ensures that, with probability higher than $1 - \delta$, we are able to build the $\Upsilon^*$ subsamples and we are in position to apply Theorem 2.3 with subGaussian norm $\zeta/|\lambda_-|^{1/2}$. Hence, with probability higher than $1 - c' \log^9(\text{nd}\lambda_-^{1/2}/(\delta\zeta_-))\delta$, we have

$$ \begin{aligned} \|M_{\hat{\pi}_{WMP}^{-1}} - M_{\pi^{*-1}}\|_F^2 &\le c \log^{11} \left( \frac{nd|\lambda_-|^{1/2}}{\delta\zeta_-} \right) \mathcal{R}_F(n, d, \zeta|\lambda_-|^{-1/2}) \\ &\le c' \log^{c''} \left( \frac{nd\lambda^{1/2}}{\zeta_-} \right) \mathcal{R}_F(n, d, \zeta|\lambda_-|^{-1/2}), \end{aligned} $$

where we use the definition of $\delta$ and $\lambda_-$ in the last line. On the complementary event, we simply use that $\|M_{\hat{\pi}_{WMP}^{-1}} - M_{\pi^{*-1}}\|_F^2 \le nd$. Since $\delta$ has been chosen small enough, we can conclude that

$$ \mathbb{E}[\|M_{\hat{\pi}_{WMP}^{-1}} - M_{\pi^{*-1}}\|_F^2] \le c' \log^{c''} \left( \frac{nd\lambda^{1/2}}{\zeta_-} \right) \mathcal{R}_F(n, d, \zeta\lambda^{-1/2}). $$

It remains to consider the case where $\lambda_- \in [2/d, 1]$. Working under the event of probability higher than $1 - \delta$ ensured by Lemma 4.2, we have $\Upsilon^*$ independent samples $Y^{(0)}, \dots, Y^{(\Upsilon^{*-1})}$ of size $n \times [d/l(\lambda)]$. Define the matrix $M^\downarrow$ of size $n \times [d/l(\lambda)]$ by $M_{i,j}^\downarrow = M_{i,l(\lambda)(j-1)+1}$. Obviously, $M_{\pi^{*-1}}$ is a bi-isotonic matrix. Besides, for $s = 0, \dots, \Upsilon^* - 1$, $(i, j) \in [n] \times [d/l(\lambda)]$, we have the decomposition

$$ Y_{ij}^{\downarrow(s)} = M_{ij}^{\downarrow(s)} + E_{ij}^{\downarrow(s)}, $$

where $M_{ij}^{\downarrow(s)}$ belongs to $[M_{ij}^\downarrow, M_{ij+1}^\downarrow]$ with the convention $M_{i,|d/l(\lambda)|+1}^{\downarrow(s)} = 1$ and the $E_{ij}^{\downarrow(s)}$'s are independent and, for fixed $i$ and $j$, are i.i.d. distributed and $\zeta$-subGaussian. In fact, the $M_{ij}^{\downarrow(s)}$ are random since $M_{ij}^{\downarrow(s)}$ has been sampled uniformly in $\{M_{i,l(\lambda)(j-1)+1}, M_{i,l(\lambda)(j-1)+2}, \dots, M_{i,l(\lambda)(j-1)+l(\lambda)}\}$. Besides, those are correlated with the noise $E_{ij}^{\downarrow(s)}$. For the sake of the analysis, it is in fact easier to consider that $M_{ij}^{\downarrow(s)}$ has been set by an adversary. Hence, we fall into the semi-random
model of Section H and we are in position to apply Theorem H.1 to $\hat{\pi}_{WM-SR}$. With probability at least $1 - c'n \log^9(\frac{nd}{\delta\zeta})\delta$, we have

$$ \|M_{\hat{\pi}_{WM-SR}^{-1}}^{\downarrow} - M_{\pi^{*-1}}^{\downarrow}\|_{F}^{2} \leq c \log^{11} \left(\frac{2nd}{\delta\zeta_{-}}\right) \left[\mathcal{R}_{F}(n, \lfloor d/l(\lambda) \rfloor, \zeta) + n\right], $$

Define the matrix $M^{\downarrow\uparrow}$ of size $n \times d$ such that each column is duplicated $l(\lambda)$ times, except the last one which has been duplicated $l(\lambda) - l(\lambda)\lfloor d/l(\lambda) \rfloor$. We readily deduce that

$$ \|M_{\hat{\pi}_{WM-SR}^{-1}}^{\downarrow\uparrow} - M_{\pi^{*-1}}^{\downarrow\uparrow}\|_{F}^{2} \leq c'l(\lambda) \log^{11} \left(\frac{2nd}{\delta\zeta_{-}}\right) \left[\mathcal{R}_{F}(n, \lfloor d/l(\lambda) \rfloor, \zeta) + n\right], \quad (116) $$

By triangular inequality, we have

$$ \|M_{\hat{\pi}_{WM-SR}^{-1}} - M_{\pi^{*-1}}\|_{F}^{2} \leq 2\|M_{\hat{\pi}_{WM-SR}^{-1}}^{\downarrow\uparrow} - M_{\pi^{*-1}}^{\downarrow\uparrow}\|_{F}^{2} + 8\|M - M^{\downarrow\uparrow}\|_{F}^{2}. $$

Thus it remains to upper bound the square Euclidean norm of each row of $M - M^{\downarrow\uparrow}$:

$$
\begin{align*}
\sum_{j=1}^{d} [M - M^{\downarrow\uparrow}]_{i,j}^{2} &= \sum_{k=1}^{\lfloor d/l(\lambda) \rfloor} \sum_{r=1}^{l(\lambda)} [M_{i,(k-1)l(\lambda)+r} - M_{i,(k-1)l(\lambda)+1}]^{2} \\
&\quad + \sum_{r=1}^{d-l(\lambda)\lfloor d/l(\lambda) \rfloor} [M_{i,((\lfloor d/l(\lambda) \rfloor-1)l(\lambda)+r) - M_{i,((\lfloor d/l(\lambda) \rfloor-1)l(\lambda)+1)}]^{2} \\
&\leq \sum_{k=1}^{\lfloor d/l(\lambda) \rfloor} l(\lambda)[M_{i,kl(\lambda)} - M_{i,(k-1)l(\lambda)+1}]^{2} + l(\lambda)[M_{i,d} - M_{i,((\lfloor d/l(\lambda) \rfloor-1)l(\lambda)+1)}]^{2} \\
&\leq 2l(\lambda),
\end{align*}
$$

since the total variation of the $i$-th row of $M$ is at most one. Hence, $\|M - M^{\downarrow\uparrow}\|_{F}^{2} \leq 2nl(\lambda)$. Together with (116), we conclude that

$$ \|M_{\hat{\pi}_{WM-SR}^{-1}} - M_{\pi^{*-1}}\|_{F}^{2} \leq c'l(\lambda) \log^{11} \left(\frac{2nd}{\delta\zeta_{-}}\right) \left[\mathcal{R}_{F}(n, \lfloor d/l(\lambda) \rfloor, \zeta) + n\right]. $$

with probability at least $1 - c'n \log^9(\frac{nd}{\delta\zeta})\delta$. Since $\delta$ has been chosen small enough and since $\|M_{\hat{\pi}_{WM-SR}^{-1}} - M_{\pi^{*-1}}\|_{F}^{2} \leq nd$, we conclude that

$$ \mathbb{E} \left[ \| M_{\hat{\pi}_{WM-SR}^{-1}} - M_{\pi^{*-1}} \|_{F}^{2} \right] \leq c' l(\lambda) \log^{11} \left( \frac{2nd}{\zeta_{-}} \right) \left[ \mathcal{R}_{F}(n, \lfloor d/l(\lambda) \rfloor, \zeta) + n \right]. $$

Since $l(\lambda) \leq c' \log^{c''}(nd(\lambda \vee 1)/\zeta)/\lambda$, we deduce from this bound that

$$
\begin{align*}
\mathbb{E} \left[ \| M_{\hat{\pi}_{WM-SR}^{-1}} - M_{\pi^{*-1}} \|_F^2 \right] & \le c' \log^{c''} \left( \frac{2nd}{\zeta_-} \right) \left[ \left( \frac{\zeta}{\sqrt{\lambda}} \right)^2 \left\{ \frac{nd^{1/6}}{\left(\frac{\zeta}{\sqrt{\lambda}}\right)^{1/3}} \wedge \frac{n^{3/4}d^{1/4}}{\left(\frac{\zeta}{\sqrt{\lambda}}\right)^{1/2}} \wedge n\sqrt{d\lambda} \wedge \frac{n^{2/3}\sqrt{d\lambda}^{1/3}}{\left(\frac{\zeta}{\sqrt{\lambda}}\right)^{1/3}} + n \right\} + \frac{n}{\lambda} \right] \\
& \le c' \log^{c''} \left( \frac{2nd}{\zeta_-} \right) \left[ \mathcal{R}_F[n, d, \zeta/\sqrt{\lambda}] + \frac{n}{\lambda} \right],
\end{align*}
$$

since $\lambda_- \leq 1$. Again, since $\lambda_- \leq 1$, we have $\lambda \leq c_3 \log^{c_4}(nd(\lambda \vee 1)/\zeta)$ for some numerical constant $c_3$ and $c_4$. We conclude that

$$ \mathbb{E} \left[ \| M_{\hat{\pi}_{WM-SR}^{-1}} - M_{\pi^{*-1}} \|_F^2 \right] \leq c' \log^{c''} \left( \frac{2nd}{\zeta_{-}} \right) \left[ \mathcal{R}_F[n, d, \zeta/\sqrt{\lambda}] + \frac{n}{\lambda} e^{-\frac{\lambda}{c_3 \log^{c_4}(nd(\lambda \vee 1)/\zeta)}} \right], $$

which concludes the proof.
# Appendix H: Permutation estimation in the semi-random model

## H.1. Model and Algorithm

We now consider a slightly different model with $\Upsilon^*$ samples $Y^{(1)}, \dots, Y^{(\Upsilon^{*-1})}$. The noise matrices $E^{(1)}, \dots, E^{(\Upsilon^{*-1})}$ are sampled independently (as previously) and $Y_{ij}^{(t)} = E_{ij}^{(t)} + M_{ij}^{(t)}$ where $M_{ij}^{(t)}$ is chosen by an adversary in $[M_{ij}, M_{i,j+1}]$. This slightly different model is mainly motivated by the analysis of the partial observation scheme in Section 4. In particular, building upon this model and relying on the corresponding modifications in the algorithm allows us to recover the right dependency with respect to $\zeta$ in Section 4.

We consider a slight variant $\hat{\pi}_{WM-SR}$ of the estimator $\hat{\pi}_{WM}$ to handle the adversarial differences. The procedure $\hat{\pi}_{WM-SR}$ is computed exactly as $\hat{\pi}_{WM}$ except that

* In **Pivot** (Algorithm 4), the threshold $\beta_{\text{tris}}\sqrt{\log(\frac{2|P|}{\delta})}$ is replaced by $\beta_{\text{tris}}\sqrt{\log(\frac{2|P|}{\delta})} + 4\|\omega\|_{\infty}/\|\omega\|_2$ and $\bar{\beta}_{\text{tris}}\sqrt{\log(\frac{2|P|}{\delta})}$ is replaced by $\bar{\beta}_{\text{tris}}\sqrt{\log(\frac{2|P|}{\delta})} + 8\|\omega\|_{\infty}/\|\omega\|_2$

* In **DimensionReduction-WM** (Algorithm 13), we respectively replace the definitions of the CUSUM and empirical width by

$$ \hat{\Delta}_{k,r'}^{(\text{ext})}(\mathcal{V}^+, \mathcal{V}^-) = \sum_{k'=k-r'}^{k+r'-1} \bar{y}_{k'}(\mathcal{V}^+) - \bar{y}_{k'-1}(\mathcal{V}^-); \quad (117) $$

$$ \hat{\mathbf{C}}_{k,r'}^{(\text{ext})}(\mathcal{V}) = \sum_{k'=k}^{k+r'-1} \bar{y}_{k'}(\mathcal{V}) - \sum_{k'=k-r'-1}^{k-2} \bar{y}_{k'}(\mathcal{V}). \quad (118) $$

**Theorem H.1.** There exist three numerical constants $c$, $c'$, and $c_0$ such that the following holds. Fix $\delta > 0$ and assume that $\Upsilon \ge c_0 \log^8(\text{nd}/(\delta\zeta_-))$. For any permutation $\pi^* \in \Pi_n$ and any matrix $M$ such that $M_{\pi^{*-1}} \in \mathbb{C}_{\text{BISO}}$, the hierarchical sorting tree estimator with memory $\hat{\pi}_{WM-SR}$ satisfies

$$ \| M_{\hat{\pi}_{WM-SR}^{-1}} - M_{\pi^{*-1}} \|_F^2 \le c \log^{11} \left( \frac{2nd}{\delta\zeta_-} \right) [\mathcal{R}_F(n, d, \zeta) + n] , \quad (119) $$

with probability at least $1 - c'n \log^9(\frac{nd}{\delta\zeta_-})\delta$.

## H.2. Proof of Theorem H.1

The proof follows the main steps as that of Theorem 2.3 and we mainly emphasize here the differences. In the proof of Theorem 2.3, we often work with the aggregated model (50) $Z = \Theta + N$ which is restricted to a subset $P$ of experts and a subset $Q \subset Q_r$ of questions aggregated at scale $r$ – see **Encode–Matrix** for details. For $t = 0, \dots, \Upsilon - 1$, the counterpart of (50) is the following

$$ Z^{(t)} = \Theta^{(t)} + N^{(t)}, \quad (120) $$

where the entries of $N^{(t)}$ are independent and $\zeta$-subGaussian and $\Theta^{(t)}$ stands for the corresponding aggregation of the matrix $M^{(t)}$. Since the total variation of each row of $M$ is at most one, one readily checks that

$$ \sum_{j \in Q} |\Theta_{ij}^{(t)} - \Theta_{ij}| \le 1. \quad (121) $$

Since $\hat{\pi}_{WM-SR}$ is a hierarchical sorting tree estimator, we are in position to control its loss using Proposition B.1. For this purpose, we need to prove that Proposition B.3 still holds
in the semi-random model which, in turn, would imply that Corollary B.4 is true. In fact, the proof of Proposition B.3 is verbatim the same except that Lemma C.1 is replaced by the following lemma.

We remind that $P' = \overline{P} \setminus (L \cup U)$, and $\overline{P}' = \overline{P} \setminus (\overline{L} \cup \overline{U})$.

**Lemma H.2.** For any non-zero vector $w \in \mathbb{R}_+^Q$, any pivot $\gamma \in \{1, \dots, |\overline{P}|\}$, we have $\mathbb{P}[\mathcal{P}_3] \ge 1 - \delta$. Besides, on the same event of probability at least $1 - \delta$, we have

$$ \left| \langle \Theta_{i,\cdot} - \Theta_{i,\gamma,\cdot}, \frac{w}{\|w\|_2} \rangle \right| \le (2\zeta\sqrt{2} + \bar{\beta}_{\text{tris}}) \sqrt{\log\left(\frac{2|\overline{P}|}{\delta}\right)} + 10 \frac{\|w\|_{\infty}}{\|w\|_2} \quad \text{if } i \in P' . \quad (122) $$

*Proof of Lemma H.2.* Consider any sample $t \in [0, \Upsilon - 1]$, any vector $w \in \mathbb{R}^q$, and any $i \in \overline{P}$. As a straightforward consequence of (121), we deduce that

$$ \left| \langle \Theta_{i,\cdot}^{(t)} - \Theta_{i,\cdot}, \frac{w}{\|w\|_2} \rangle \right| \le \frac{\|w\|_{\infty}}{\|w\|_2} . \quad (123) $$

We then deduce from a union bound, that with probability higher than $1 - \delta$, we have

$$ \left| \langle Z_{i,\cdot}^{(t)}, \frac{w}{\|w\|_2} \rangle - \langle \Theta_{i,\cdot}, \frac{w}{\|w\|_2} \rangle \right| \le \zeta \sqrt{2 \log \left( \frac{2|\overline{P}|}{\delta} \right)} + \frac{\|w\|_{\infty}}{\|w\|_2} . $$

simultaneously for all $i$ in $\overline{P}$. The rest of the proof of Lemma H.2 is left unchanged provided that we replace $\sqrt{2 \log \left( \frac{2|\overline{P}|}{\delta} \right)}$ by $\sqrt{2 \log \left( \frac{2|\overline{P}|}{\delta} \right)} + \frac{\|w\|_{\infty}}{\|w\|_2}$. $\square$

Then, being in position to apply Corollary B.4, we state the counterpart of Proposition B.6.

**Proposition H.3.** On the intersection of event $\xi$ (defined in Corollary B.4) and an event of probability higher than $1 - 5 \cdot 2^t \tau_{\infty} \delta$, it holds that

$$ \sum_{\overline{P} \in \mathcal{L}_t} \|M(\overline{P}) - \overline{M}(\overline{P})\|^2 \lesssim \log^9 \left( \frac{6nd}{\delta\zeta_-} \right) [\mathcal{R}_F(n, d, \zeta) + n] . $$

We conclude the proof of Theorem H.1 by combining Proposition H.3 with Corollary B.4. Hence, we only need to prove the last proposition.

### H.3. Proof of Proposition H.3

Again, we only emphasize the differences with the proof of Proposition B.6. We start with the analysis of **DimensionReduction – WM**. Recall that we slightly changed the definition of the CUSUM statistics

$$ \bar{\mathbf{C}}_{k,2r_{\text{cp}}}^{(\text{ext})} = \frac{1}{2r_{\text{cp}}} \left( \sum_{k'=k}^{k+2r_{\text{cp}}-1} \bar{y}_{k'}(\mathcal{V}_{2r_{\text{cp}}}) - \sum_{k'=k-2r_{\text{cp}}-1}^{k-2} \bar{y}_{k'}(\mathcal{V}_{2r_{\text{cp}}}) \right) $$

by shifting the second sum by one index. The definition of the population CUSUM statistic $\mathbf{C}_{k,2r_{\text{cp}}}^{*(\text{ext})}$ is left unchanged. Similarly, we slightly changed the definition of $\bar{\Delta}_{k,r_{\text{cp}}}^{(\text{ext})}$ to

$$ \bar{\Delta}_{k,r_{\text{cp}}}^{(\text{ext})} = \frac{1}{2r_{\text{cp}}} \sum_{k'=k-r_{\text{cp}}}^{k+r_{\text{cp}}-1} \bar{y}_{k'}(\mathcal{V}_{r_{\text{cp}}}^{+}) - \bar{y}_{k'-1}(\mathcal{V}_{r_{\text{cp}}}^{-}) , $$
by shifting again the right hand-side observation by one. With these simple shifts, $\hat{\Delta}_{k,r_{cp}}^{(\text{ext})}$ and $\hat{\mathbf{C}}_{k,2r_{cp}}^{(\text{ext})}$ both overestimates $\Delta_{k,r_{cp}}^{(\text{ext})}$ and $\mathbf{C}_{k,2r_{cp}}^{(\text{ext})}$ and arguing as in the proof of Lemma F.1, we will prove that $Q_{WM}^* \subset \hat{Q}_{WM}$ with probability at least $1 - \delta$ -see Lemma H.4 below. However, we need to adapt the definition of $\overline{D}_{WM}^*(T, P, h, r, r_{cp})$ to cope with this possible bias. Define

$$ \overline{D}_{WM-SR-1}^*(T, P, h, r, r_{cp}) = \{k \in 1, \dots, d : \mathbf{C}_{k,2r_{cp}}^{*(\text{ext})} \ge \frac{h}{128} \text{ and } \Delta_{k,r_{cp}}^{*(\text{ext})} \ge \frac{h}{128}\}; \quad (124) $$

$$ \overline{D}_{WM-SR-2}^*(T, P, h, r, r_{cp}) = \{k \in 1, \dots, d : \overline{m}_{k+r_{cp}}(\mathcal{V}_{r_{cp}}^+) - \overline{m}_{k-r_{cp}}(\mathcal{V}_{r_{cp}}^+) \ge \frac{hr_{cp}}{128}\}; \quad (125) $$

$$ \overline{D}_{WM-SR-3}^*(T, P, h, r, r_{cp}) = \{k \in 1, \dots, d : \overline{m}_{k+r_{cp}-1}(\mathcal{V}_{r_{cp}}^{-}) - \overline{m}_{k-r_{cp}-1}(\mathcal{V}_{r_{cp}}^{-}) \ge \frac{hr_{cp}}{128}\}; \quad (126) $$

$$ \overline{D}_{WM-SR-4}^*(T, P, h, r, r_{cp}) = \{k \in 1, \dots, d : \overline{m}_{k+2r_{cp}}(\mathcal{V}_{2r_{cp}}) - \overline{m}_{k-2r_{cp}-1}(\mathcal{V}_{2r_{cp}}) \ge \frac{hr_{cp}}{128}\}. \quad (127) $$

Then, we define the corresponding subsets $\overline{Q}_{WM-SR-1}^*, \overline{Q}_{WM-SR-2}^*, \overline{Q}_{WM-SR-3}^*$, and $\overline{Q}_{WM-SR-4}^*$ of $Q_r$. For short, we write $\overline{Q}_{WM-SR}^* = \overline{Q}_{WM-SR-1}^* \cup \overline{Q}_{WM-SR-2}^* \cup \overline{Q}_{WM-SR-3}^* \cup \overline{Q}_{WM-SR-4}^*$. We have the following counterpart of Lemma F.1.

**Lemma H.4.** Consider any valid hierarchical sorting tree $\mathcal{T}$, any subset $P$ of a leaf $G$ of $\mathcal{T}$, any $h \in \mathcal{H}$, and any $r \in \mathcal{R}$. With probability at least $1 - \delta$, it holds that

$$ Q_{WM}^* \subset \overline{Q}_{WM}^* \subset \overline{Q}_{WM-SR}^* \quad (128) $$

Obviously, Lemma F.2 is still true since it does not depend on the data generating process. Then, we adapt Propositions D.4 and D.5 to this adversarial setting.

**Proposition H.5.** Consider any $\overline{P} \subset [n]$, any $r \in \mathcal{R}$, and any subset $Q \subset Q_r$. Also, fix any $\eta > 0$ and any $\phi > 0$. Provided that

$$ \| [\Theta(\overline{P}, Q) - \overline{\Theta}(\overline{P}, Q)]_{\eta} \|_{F}^{2} \ge \frac{1}{\phi} \| \Theta(\overline{P}, Q) - \overline{\Theta}(\overline{P}, Q) \|_{F}^{2} \ge 8\eta |\overline{P}| \left[ \phi_{l_1} \sqrt{\log\left(\frac{2|\overline{P}|}{\delta}\right)} \sqrt{|\overline{Q}|} + 20 \right], $$

then, with probability higher than $1 - \delta$, we have

$$ \|\Theta(\overline{P}', Q) - \overline{\Theta}(\overline{P}', Q)\|_F^2 \le \left(1 - \frac{1}{16\phi}\right) \|\Theta(\overline{P}, Q) - \overline{\Theta}(\overline{P}, Q)\|_F^2. $$

Recall the definition (60) of $\phi_{l_1}$. Henceforth, the matrix $\Theta(\overline{P}, Q)$ is said to be indistinguishable in $l_1$-norm if it satisfies

$$ \max_{i,j \in \overline{P}} \| \Theta_{i,j}(\overline{P}, Q) - \Theta_{j,i}(\overline{P}, Q) \|_1 \le \phi_{l_1} \sqrt{|Q| \log\left(\frac{2|\overline{P}|}{\delta}\right) + 20}. \quad (129) $$

**Proposition H.6.** Let $\overline{P} \subset [n]$ and $Q \subset [d]$. If $\Theta(\overline{P}, Q)$ is indistinguishable in $l_1$-norm and if

$$ \|\Theta(\overline{P}, Q) - \overline{\Theta}(\overline{P}, Q)\|_F^2 \ge 10^6 \log^3 \left(\frac{6nd}{\delta\zeta_{-}}\right) \left[ \zeta^2 \left(\sqrt{|\overline{P}\|Q|} + |\overline{P}|\right) + |\overline{P}| \right], \quad (130) $$

then, with probability higher than $1 - 3\delta$, we have

$$ \|\Theta(\overline{P}', Q) - \overline{\Theta}(\overline{P}', Q)\|_F^2 \le \left(1 - \frac{1}{200 \log^2(\text{nd}/\zeta_{-})}\right) \|\Theta(\overline{P}, Q) - \overline{\Theta}(\overline{P}, Q)\|_F^2. $$
Equipped with these two propositions, we arrive at the counterpart of Propositions D.7 and F.3. Recall Definition (64) of the function $\Psi$ by $\Psi(p, r, h, q) = \frac{hp\sqrt{rq}}{\zeta} \wedge \sqrt{pq} + p$.

**Proposition H.7.** Assume that $\mathcal{T}_t$ is a valid hierarchical sorting tree. Consider a leaf $G$ of $\mathcal{T}$ of type **0** or **1** at depth $t$. With probability higher than $1 - 5\tau_\infty\delta$, there exists a subset $\bar{P}^\dagger$ such that $\bar{P} \subseteq \bar{P}^\dagger \subseteq G$ and the following property holds. For some $r_{cp}^\dagger \ge r^\dagger \in \mathcal{R}$ and some $h^\dagger \in \mathcal{H}$, upon writing $Q_{WM}^\dagger = Q_{WM}^*$ and $\bar{Q}_{WM-SR}^\dagger = \bar{Q}_{WM-SR}^*$, we have simultaneously

$$ \| [\Theta(\bar{P}^\dagger, Q_{WM-SR}^\dagger) - \bar{\Theta}(\bar{P}^\dagger, Q_{WM}^\dagger)]_{\sqrt{r^\dagger h^\dagger}} \|_F^2 \le 2 \cdot 10^6 \log^3 \left( \frac{6nd}{\delta\zeta_-} \right) \left[ \zeta^2 \Psi(|\bar{P}^\dagger|, r^\dagger, h^\dagger, |\bar{Q}_{WM-SR}^\dagger|) + |\bar{P}^\dagger| \right] ; \quad (131) $$

$$ \| M(\bar{P}^\dagger) - \bar{M}(\bar{P}^\dagger) \|_F^2 \le 16\zeta^2 + 96|\mathcal{R}\|\mathcal{H}\| [\Theta(\bar{P}^\dagger, Q_{WM}^\dagger) - \bar{\Theta}(\bar{P}^\dagger, Q_{WM}^\dagger)]_{\sqrt{r^\dagger h^\dagger}} \|_F^2 . \quad (132) $$

The proof is analogous to that of Proposition F.3, up to some numerical constants, and is omitted.

Then, we state the counterpart of Lemma F.4 to control $|\bar{Q}_{WM-SR}^\dagger|$. In comparison to this lemma, we have an additional term $n/(prh)$.

**Lemma H.8.** Assume that $\mathcal{T}_t$ is a valid hierarchical sorting tree. For any $h \in \mathcal{H}$, $r \in \mathbb{R}$, any integer $p$, any sequence $\bar{P}_v$ of subsets of $G_v$, it holds that

$$ \sum_{\bar{P} \in \mathcal{P}^*(p)} |\bar{Q}_{WM-SR}^*(\bar{P}, h, r)| \le \log(d) \left[ \left\{ \frac{\sqrt{nd(r_0 \vee r)}}{rh\sqrt{p}} \wedge \frac{d(r_0 \vee r)}{r^2h} \wedge \frac{nd}{pr} \wedge \frac{n(r_0 \vee r)}{prh} \right\} + \frac{n}{prh} \right] . \quad (133) $$

Then, we apply Proposition H.7 to control the loss on an additional event of probability higher than $1 - 5 \cdot 2^t \tau_\infty \delta$.

$$ \begin{aligned} & \sum_{\bar{P} \in \mathcal{L}_t} \| M(\bar{P}) - \bar{M}(\bar{P}) \|_F^2 \\ & \le 16\zeta^2 |\bar{\mathcal{L}}_t| + 96|\mathcal{R}\|\mathcal{H}| \sum_{p,h,r} \sum_{\bar{P}^\dagger \in \mathcal{P}^*(p,h,r)} \| [\Theta(\bar{P}^\dagger, \bar{Q}_{WM}^\dagger) - \bar{\Theta}(\bar{P}^\dagger, \bar{Q}_{WM}^\dagger)]_{\sqrt{rh}} \|_F^2 \\ & \lesssim \log^5 \left( \frac{6nd}{\delta\zeta_-} \right) \sum_{p,h,r} \sum_{\bar{P}^\dagger \in \mathcal{P}^*(p,h,r)} \left[ \zeta^2 \sqrt{\left[ \frac{h^2pr}{\zeta^2} \wedge 1 \right] p |\bar{Q}_{WM}^*(\bar{P}^\dagger, h, r)|} + (\zeta^2 \vee 1)p \right] \\ & \lesssim \log^{5.5} \left( \frac{6nd}{\delta\zeta_-} \right) \sum_{p,h,r} \left[ \zeta^2 \sqrt{\frac{nr}{r \vee r_0} \sum_{\bar{P}^\dagger \in \mathcal{P}^*(p,h,r)} |\bar{Q}_{WM}^*(\bar{P}^\dagger, h, r)|} + (\zeta^2 \vee 1)n \right] \\ & \lesssim \log^6 \left( \frac{6nd}{\delta\zeta_-} \right) \sum_{p,h,r} \left[ \zeta^2 \left( n^{3/4} d^{1/4} \left( \frac{1}{(r_0 \vee r)ph^2} \right)^{1/4} \wedge n \sqrt{\frac{d}{p(r_0 \vee r)}} \wedge \frac{n}{\sqrt{ph}} \wedge \sqrt{\frac{nd}{rh}} \right) + \zeta^2 n \sqrt{\frac{1}{pr_0h}} + (\zeta^2 \vee 1)n \right] \\ & \stackrel{(a)}{\lesssim} \log^7 \left( \frac{6nd}{\delta\zeta_-} \right) \sum_{p,h} \left[ \zeta^2 \left( \frac{n^{3/4}d^{1/4}}{\zeta^{1/2}} \wedge n\sqrt{d} \wedge \frac{nh}{\zeta}\sqrt{d} \wedge \frac{n}{\sqrt{h}} \wedge \frac{\sqrt{nd}}{\sqrt{h}} \right) + (\zeta^2 \vee 1)n \right] \\ & \lesssim \log^9 \left( \frac{6nd}{\delta\zeta_-} \right) \left[ \zeta^2 \left( \frac{n^{3/4}d^{1/4}}{\zeta^{1/2}} \wedge n\sqrt{d} \wedge \frac{n^{2/3}\sqrt{d}}{\zeta^{1/3}} \wedge \frac{nd^{1/6}}{\zeta^{1/3}} \right) + (\zeta^2 \vee 1)n \right], \end{aligned} $$

where, in (a), we use that $pr_0h \ge pr_0h^2 \gtrsim 1$, the rest of the bounds being analogous to the proof of Proposition H.3. This concludes the proof.
### H.4. Proofs of the lemmas

**Proof of Lemma H.4.** By a union bound and arguing as in the proof of Lemma F.1, we deduce that, with probability higher than $1 - \delta$, we have simultaneously

$$ \max_{r_{cp} \in [4r, \bar{r}] \cap \mathcal{R}} \max_{k \in [d]} |\hat{\mathbf{C}}_{k, 2r_{cp}}^{*(\text{ext})} - \mathbb{E}[\hat{\mathbf{C}}_{k, 2r_{cp}}^{*(\text{ext})}]| \le h/32; \quad (134) $$

$$ \max_{r_{cp} \in [4r, \bar{r}] \cap \mathcal{R}} \max_{k \in [d]} |\hat{\mathbf{\Delta}}_{k, r_{cp}}^{*(\text{ext})} - \mathbb{E}[\hat{\mathbf{\Delta}}_{k, r_{cp}}^{*(\text{ext})}]| \le h/32. \quad (135) $$

Because of the adversarial observations, we now have

$$ \begin{aligned} \mathbf{C}_{k, 2r_{cp}}^{*(\text{ext})} &\le \mathbb{E}[\hat{\mathbf{C}}_{k, 2r_{cp}}^{*(\text{ext})}] \le \mathbf{C}_{k, 2r_{cp}}^{*(\text{ext})} + \frac{\bar{m}_{k+2r_{cp}}(\mathcal{V}) - \bar{m}_{k-2r_{cp}-1}(\mathcal{V})}{2r_{cp}}, \\ \hat{\mathbf{\Delta}}_{k, r_{cp}}^{*(\text{ext})} &\le \mathbb{E}[\hat{\mathbf{\Delta}}_{k, r_{cp}}^{*(\text{ext})}] \le \hat{\mathbf{\Delta}}_{k, r_{cp}}^{*(\text{ext})} + \frac{\bar{m}_{k+r_{cp}}(\mathcal{V}^+) - \bar{m}_{k-r_{cp}-1}(\mathcal{V}^-)}{2r_{cp}} + \frac{\bar{m}_{k+r_{cp}-1}(\mathcal{V}^+) - \bar{m}_{k-r_{cp}}(\mathcal{V}^-)}{2r_{cp}}. \end{aligned} $$

Combining the above bounds with (134) and (135) allows us to conclude. □

**Proof of Proposition H.5.** With the notation of the proof of Proposition D.4, the condition (71) is now replaced by

$$ \max_{i,j \in \bar{P}'} \|\Theta(\bar{P}')_{i,\cdot} - \Theta(\bar{P}')_{j,\cdot}\|_1 \le \Phi_{l_1} \sqrt{|\bar{Q}|} + 20, \quad (136) $$

where we used Lemma H.2 with $w = \mathbf{1}_Q$. The rest of the proof is left unchanged except that we replace $\Phi_{l_1} \sqrt{|\bar{Q}|}$ by $\Phi_{l_1} \sqrt{|\bar{Q}|} + 20$. □

**Proof of Proposition H.6.** Lemma E.4 is still true. However, Lemma E.5 needs to be updated to

**Lemma H.9.** Fix any $\delta \in (0, 1)$. If

$$ \|\Theta - \bar{\Theta}\|_{\text{op}}^2 \ge 6400 \left[ |\tilde{P}| + \zeta^2 \left[ \sqrt{|\bar{Q}|(5|\tilde{P}| + \log(6/\delta))} + 7|\tilde{P}| + 2\log(6/\delta) \right] \right], \quad (137) $$

then, with probability higher than $1 - \delta$, we have

$$ \|\hat{v}^T (\Theta - \bar{\Theta})\|_2^2 \ge \frac{1}{2} \|\Theta - \bar{\Theta}\|_{\text{op}}^2. $$

In light of Condition (130), this assumption is valid. Together with Lemma E.4, we deduce that there exists an event of probability higher than $1 - \delta$ such that

$$ \|\hat{v}^T (\Theta - \bar{\Theta})\|_2^2 \ge \frac{1}{2} \|\Theta - \bar{\Theta}\|_{\text{op}}^2 \ge \frac{1}{32 \log^2(\text{nd}/\zeta_-)} \|\Theta - \bar{\Theta}\|_F^2. $$

As the vectors $\hat{z}$ and $\hat{w}$ are defined though $Z^{(3)}$, we rather focus on $\Theta^{(3)}$. By (121), we have $\|\Theta^{(3)} - \Theta\|_{\text{op}} \le \sqrt{|\tilde{P}|}$.

$$ \begin{aligned} \|\hat{v}^T(\Theta^{(3)} - \bar{\Theta}^{(3)})\|_2^2 &\ge \|\hat{v}^T(\Theta - \bar{\Theta})\|_2^2 - 4\|\Theta - \Theta^{(3)}\|_{\text{op}}\|\Theta - \bar{\Theta}\|_{\text{op}} \ge \|\hat{v}^T(\Theta - \bar{\Theta})\|_2^2 - 4\sqrt{|\tilde{P}|}\|\Theta - \bar{\Theta}\|_{\text{op}} \\ &\ge \frac{9}{20}\|\Theta - \bar{\Theta}\|_{\text{op}}^2 \ge \frac{1}{36 \log^2(\text{nd}/\zeta_-)}\|\Theta - \bar{\Theta}\|_F^2. \end{aligned} \quad (138) $$

Then, the analysis of $\hat{z}$ and $z^*$ follows the same steps as in the original proofs, - see Appendix E.3 - the main difference being that we invoke (136) instead of (71). More precisely, we still have

$$ \left| \hat{v}^T(\Theta^{(3)} - \bar{\Theta}^{(3)}) \frac{\hat{w}}{\|\hat{w}\|_2} \right|^2 \ge \frac{16}{25} \|w^*\|_2^2. \quad (139) $$
and

$$ \|w^*\|_2^2 = \|z^*\|_2^2 - \sum_{l \in S^{*c}} (z_l^*)^2. \qquad (140) $$

The control of $\sum_{l \in S^{*c}} (z_l^*)^2$ is slightly different.

$$
\begin{aligned}
\left[ \sum_{l \in S^{*c}} (z_l^*)^2 \right]^2 &= \left[ \sum_{l \in S^{*c}} [\hat{v}^T(\Theta^{(3)} - \bar{\Theta}^{(3)})]_l z_l^* \right]^2 \\
&\le \| (\Theta^{(3)} - \bar{\Theta}^{(3)}) z_{S^{*c}}^* \|_2^2 = \sum_{i \in \tilde{P}} \left( \sum_{l \in S^{*c}} (\Theta_{i,l}^{(3)} - \bar{\Theta}_l^{(3)}) z_l^* \right)^2 \\
&\le \frac{18\zeta^2}{|\tilde{P}|^2} \log\left(\frac{2|Q|}{\delta}\right) \sum_{i \in \tilde{P}} \left( \sum_{l \in S^{*c}} \sum_{j \in \tilde{P}} |\Theta_{i,l}^{(3)} - \Theta_{j,l}^{(3)}| \right)^2 \\
&\le \frac{18\zeta^2}{|\tilde{P}|^2} \log\left(\frac{2|Q|}{\delta}\right) \sum_{i \in \tilde{P}} \left( \sum_{j \in \tilde{P}} \|\Theta_{i,\cdot}^{(3)} - \Theta_{j,\cdot}^{(3)}\|_1 \right)^2 \\
&\le 18\zeta^2 \log\left(\frac{2|Q|}{\delta}\right) |\tilde{P}| \left[ \phi_{l_1} \log^{1/2}\left(\frac{2|\tilde{P}|}{\delta}\right) \sqrt{Q} + 22 \right]^2 \\
&\le \left[ 250\zeta^2 \log\left(\frac{2|Q\|\tilde{P}|}{\delta}\right) (\sqrt{|\tilde{P}||Q|} + 1) + 400|\tilde{P}| \right]^2,
\end{aligned}
$$

where we used (136) as well as the fact $\|\Theta_{i,\cdot}^{(3)} - \Theta_{i,\cdot}\|_1 \le 1$. Recall that $z^* = \hat{v}^T(\Theta^{(3)} - \bar{\Theta}^{(3)})$. Combining Appendix H.4, (140), and Condition (130), we deduce that

$$ \|w^*\|_2^2 \ge \frac{1}{72 \log^2(\text{nd}/\zeta_-)} \|\Theta - \bar{\Theta}\|_F^2, $$

which, together with (139), yields

$$ \left\| (\Theta^{(3)} - \bar{\Theta}^{(3)}) \frac{\hat{w}}{\|\hat{w}\|_2} \right\|_2^2 \ge \left| \hat{v}^T (\Theta^{(3)} - \bar{\Theta}^{(3)}) \frac{\hat{w}}{\|\hat{w}\|_2} \right| \ge \frac{1}{120 \log^2(\text{nd}/\zeta_-)} \|\Theta - \bar{\Theta}\|_F^2. $$

Then, we come back to the matrix $\Theta - \bar{\Theta}$ using again (121).

$$ \left\| (\Theta - \bar{\Theta}) \frac{\hat{w}}{\|\hat{w}\|_2} \right\|_2^2 \ge \frac{9}{10} \left| \hat{v}^T (\Theta^{(3)} - \bar{\Theta}^{(3)}) \frac{\hat{w}}{\|\hat{w}\|_2} \right| - 9|\tilde{P}|. $$

Then, we apply Harris' inequality as in the original proof of the lemma to conclude that

$$ \left\| (\Theta - \bar{\Theta}) \frac{\hat{w}^+}{\|\hat{w}^+\|_2} \right\|_2^2 \ge \left\| (\Theta - \bar{\Theta}) \frac{\hat{w}}{\|\hat{w}\|_2} \right\|_2^2 \ge \frac{9}{1200 \log^2(\text{nd}/\zeta_-)} \|\Theta - \bar{\Theta}\|_F^2 - 9p \ge \frac{1}{150 \log^2(\text{nd}/\zeta_-)} \|\Theta - \bar{\Theta}\|_F^2. \qquad (141) $$

Applying the pivot algorithm to $\hat{w}^+$, we deduce from Lemma H.2 that there exists an event of probability higher than $1 - \delta$ such that

$$ \max_{i,j \in \tilde{P}'} \left| \langle \Theta(\tilde{P}')_{i,\cdot} - \Theta(\tilde{P}')_{j,\cdot}, \frac{\hat{w}^+}{\|\hat{w}^+\|_2} \right| \le \phi_{l_1} \sqrt{\log\left(\frac{2|\tilde{P}|}{\delta}\right)} + 20. $$

By convexity, it follows that

$$ \left\| [\Theta(\tilde{P}') - \bar{\Theta}(\tilde{P}')] \frac{\hat{w}^+}{\|\hat{w}^+\|_2} \right\|_2^2 \le 2\phi_{l_1}^2 \log\left(\frac{2|\tilde{P}|}{\delta}\right) |\tilde{P}'| + 800|\tilde{P}'| \le |\tilde{P}| \left[ 2\phi_{l_1}^2 \log\left(\frac{2|\tilde{P}|}{\delta}\right) + 800 \right]. $$
In light of Condition (62), this quantity is small compared to $\|\Theta - \bar{\Theta}\|_F^2$.

$$ \|(\Theta(\bar{P}') - \bar{\Theta}(\bar{P}')) \frac{\dot{w}^+}{\|\dot{w}^+\|_2}\|_2^2 \le \frac{1}{200 \log^2(\text{nd}/\zeta_-)} \|\Theta - \bar{\Theta}\|_F^2. \quad (142) $$

Then, we conclude from (142) as we did from (83) in the original proof. □

**Proof of Lemma H.9.** For short, we write $p = |\tilde{P}|$. Since $Z^{(t)} = \Theta^{(t)} + N^{(t)}$ for $t = 1, 2$, the difference with Lemma E.5 is that $\Theta^{(1)}$ and $\Theta^{(2)}$ are involved in the terms $v^T(Z^{(1)} - \bar{Z}^{(1)})$ and $v^T(Z^{(2)} - \bar{Z}^{(2)})$. Hence, arguing as in the proof of Lemma E.5, we derive that, on an event of probability higher than $1 - 3\delta$, we have simultaneously for all $v \in \mathbb{R}^p$ with $\|v\|_2 \le 1$ that

$$ \begin{aligned} & \|v^T(Z^{(1)} - \bar{Z}^{(1)})\|_2^2 - \|v^T(\Theta^{(1)} - \bar{\Theta}^{(1)})\|_2^2 + \\ & \frac{1}{2}\|v^T(\Theta^{(1)} - \bar{\Theta}^{(1)} - \Theta^{(2)} + \bar{\Theta}^{(2)})\|_2^2 - \frac{1}{2}\|v^T(Z^{(1)} - \bar{Z}^{(1)} - Z^{(2)} + \bar{Z}^{(2)})\|_2^2 \\ & \le 10\zeta \left[ \|\Theta^{(1)} - \bar{\Theta}^{(1)}\|_{\text{op}} + \frac{1}{2}\|\Theta^{(1)} - \bar{\Theta}^{(1)} - \Theta^{(2)} + \bar{\Theta}^{(2)}\|_{\text{op}} \right] \sqrt{2p + \log(6/\delta)} \\ & \quad + 192\zeta^2 \left[ \sqrt{q(3p + \log(6/\delta))} + (3p + \log(6/\delta)) \right]. \end{aligned} $$

By (121), we have $\|\Theta^{(t)} - \Theta\|_{\text{op}} \le \sqrt{p}$ for $t = 1, 2$. Hence, the above bound simplifies in

$$ \begin{aligned} & \|v^T(Z^{(1)} - \bar{Z}^{(1)})\|_2^2 - \|v^T(\Theta - \bar{\Theta})\|_2^2 - \frac{1}{2}\|v^T(Z^{(1)} - \bar{Z}^{(1)} - Z^{(2)} + \bar{Z}^{(2)})\|_2^2 \\ & \le 10\zeta \left[ \|\Theta - \bar{\Theta}\|_{\text{op}} + 4\sqrt{p} \right] \sqrt{2p + \log(6/\delta)} + 192\zeta^2 \left[ \sqrt{q(3p + \log(6/\delta))} + (3p + \log(6/\delta)) \right] \\ & \quad + 12p + 4\sqrt{p} \|\Theta - \bar{\Theta}\|_{\text{op}}. \end{aligned} $$

Since we assume that $\|\Theta - \bar{\Theta}\|_{\text{op}}^2 \ge 6400[p + \zeta^2[\sqrt{q(5p + \log(6/\delta))} + 7p + 2\log(6/\delta)]]$, we deduce that, on the same event, we have

$$ \sup_{v \in \mathbb{R}^p: \|v\|_2 \le 1} \left\| v^T(Z^{(1)} - \bar{Z}^{(1)}) \right\|_2^2 - \left\| v^T(\Theta - \bar{\Theta}) \right\|_2^2 - \frac{1}{2} \left\| v^T(Z^{(1)} - \bar{Z}^{(1)} - Z^{(2)} + \bar{Z}^{(2)}) \right\|_2^2 \le \frac{1}{4} \left\| \Theta - \bar{\Theta} \right\|_{\text{op}}^2. $$

The rest of the proof is left unchanged. □

**Proof of Lemma H.8.** Recall that $\bar{Q}^*_{WM-SR}(\bar{P}, h, r)$ decomposes as the union of $\bar{Q}^*_{WM-SR-1}$, $\bar{Q}^*_{WM-SR-2}$, and $\bar{Q}^*_{WM-SR-3}$, $\bar{Q}^*_{WM-SR-4}$. Since $\bar{Q}^*_{WM-SR-1}$ is defined analogously to $\bar{Q}^*_{WM}$ –but with a different numerical constant–, we can argue as in the proof of Lemma H.8, which yields

$$ \sum_{\bar{P} \in \mathcal{P}^*(p)} |\bar{Q}^*_{WM-SR-1}(\bar{P}, h, r)| \le \log(d) \left[ \frac{\sqrt{nd(r_0 \vee r)}}{rh\sqrt{p}} \wedge \frac{d(r_0 \vee r)}{r^2h} \wedge \frac{nd}{pr} \wedge \frac{n(r_0 \vee r)}{prh} \right]. $$

It remains to consider the three last sets. We only focus on $\bar{Q}^*_{WM-SR-2}(\bar{P}, h, r)$, the last ones being analogous. We first focus on a single set $\bar{Q}^*_{WM-SR-2}(\bar{P}, h, r, r_{\text{cp}})$. If $k$ belongs to $\bar{D}^*_{WM-SR-2}(\bar{P}, h, r, r_{\text{cp}})$, this implies that the total variation of $\bar{m}(\mathcal{V}^+_{r_{\text{cp}}})$ between $k - r_{\text{cp}}$ and $k + r_{\text{cp}}$ is at least $hr_{\text{cp}}/128$. Since the total variation of $\bar{m}(\mathcal{V}^+_{r_{\text{cp}}})$ is at most one, there are at most $c/(hr_{\text{cp}})$ regions of $Q_{r_{\text{cp}}}$ that contain at least a point $\bar{D}^*_{WM-SR-2}(\bar{P}, h, r, r_{\text{cp}})$, which entails that there are at most $c'_{r_{\text{cp}}} \cdot \frac{1}{hr_{\text{cp}}} = c'/(hr)$ regions of $Q_r$ that contain at least a point
$\overline{D}^*_{WM-SR-2}(\overline{P}, h, r, r_{cp})$. Since $r_{cp}$ takes at most a logarithmic number of values and since $|\mathcal{P}^*(p)| \le n/p$, we obtain

$$ \sum_{r_{cp}} \sum_{\overline{P} \in \mathcal{P}^*(p)} |\overline{Q}^*_{WM-SR-2}(\overline{P}, h, r, r_{cp})| \le \log(d) \frac{n}{prh}, $$

which concludes the proof. □

## Appendix I: Proofs for the $l_\infty$ loss

*Proof of Lemma 4.5.* Without loss of generality, we assume that $\pi^*$ is the identity. Fix any $i \in [n]$ and assume that $\hat{\pi}^{-1}(i) \neq i$. Consider for instance the case where $m = \hat{\pi}^{-1}(i) > i$. As a consequence, there are at least $l = m - i$ experts that are below $m$ in the oracle order and above $m$ in the estimated order. Denote $j$ the smallest of those experts. Hence, we have $j \le i < m$ and $\hat{\pi}(j) \ge \hat{\pi}(m)$. Besides, since $j \le i \le m$, we deduce from the bi-isotonic assumption that

$$ \|M_{i,..} - M_{\hat{\pi}^{-1}(i),..}\|_2^2 \le \|M_{j,..} - M_{\hat{\pi}^{-1}(j),..}\|_2^2 = \|M_{j,..} - M_{m,..}\|_2^2. $$

Taking the supremum over all $i$ implies that $l_\infty(\hat{\pi}, \pi^*) \le l_{err}(\hat{\pi}, \pi^*)$. Let us turn to the second inequality. Consider any $i < j$ such that $\hat{\pi}(i) > \hat{\pi}(j)$. We consider three subcases.

(i) If $\hat{\pi}(i) \ge j$, then we have $\|M_{i,..} - M_{j,..}\|_2^2 \le \|M_{i,..} - M_{\hat{\pi}(i),..}\|_2^2$.

(ii) If $\hat{\pi}(j) \le i$, then $\|M_{i,..} - M_{j,..}\|_2^2 \le \|M_{\hat{\pi}(j),..} - M_{j,..}\|_2^2$.

(iii) It remains to consider the case where we have $i < \hat{\pi}(j) < \hat{\pi}(i) < j$. As a consequence, for each $k \in [d]$, we have $M_{j,k} - M_{i,k} \le M_{j,k} - M_{\hat{\pi}(j),k} + M_{\hat{\pi}(i),k} - M_{i,k}$, which in turn implies that

$$ \|M_{j,..} - M_{i,..}\|_2^2 \le 4l_\infty(\hat{\pi}, \pi^*) . $$

Taking the supremum over all $i$ and reminding the definition of $j$ concludes the proof. □

*Proof of Proposition 4.6.* For $n = 2$, all the losses are equal. Hence, the minimax lower bound (34) is a straightforward consequence of the general minimax lower bound of Theorem 4.1 by a reduction to the case where $n = 2$ (recall that $\zeta = 1$ here) - This reduction is achieved by putting to 0 the signal corresponding to all $n - 2$ experts that do not corresponds to the 2 experts of interest that will be most difficult to distinguish so that estimating the permutation amounts to deciphering between these two experts. Hence, we derive that

$$ \inf_{\hat{\pi}} \sup_{\pi^* \in \Pi_n} \sup_{M: M_{\pi^{*-1}} \in \mathbb{C}_{\text{BISO}}} \mathbb{E}_{(\pi^*, M)}[l_\infty(\hat{\pi}, \pi^*)] \ge c'' \left[ \left( \frac{d^{1/6}}{\lambda^{5/6}} \wedge \frac{\sqrt{d}}{\lambda} + \frac{1}{\lambda} \right) \wedge d \right]. $$

It turns out that the term $1/\lambda$ is higher than $d$ if $\lambda \le 1/d$ and is smaller than $\frac{d^{1/6}}{\lambda^{5/6}} \wedge \frac{\sqrt{d}}{\lambda}$ for larger $\lambda$'s. Hence, we can conclude that

$$ \inf_{\hat{\pi}} \sup_{\pi^* \in \Pi_n} \sup_{M: M_{\pi^{*-1}} \in \mathbb{C}_{\text{BISO}}} \mathbb{E}_{(\pi^*, M)}[l_\infty(\hat{\pi}, \pi^*)] \ge c'' \left[ \frac{d^{1/6}}{\lambda^{5/6}} \wedge \frac{\sqrt{d}}{\lambda} \wedge d \right]. $$

Regarding the upper bound, we build upon the analysis of $\hat{\pi}_{WMP}$ in the specific case of $n = 2$. Consider any fixed $i$ and $j$. With probability higher than $1 - c\delta \log^{c'}[nd(\lambda \vee 1)]$, it follows from the proof of Theorems 2.3 and 4.3 that (i) $\hat{\pi}_{WMP}$ builds a valid hierarchical sorting tree and (ii) the set $\overline{P} \subset \{i, j\}$ built at the end of **BlockSort** satisfies

$$ \|M(\overline{P}) - \overline{M}(\overline{P})\|_F^2 \le c_1 \log^{c_2} (nd(\lambda \vee 1)) \left[ \frac{d^{1/6}}{\lambda^{5/6}} \wedge \frac{\sqrt{d}}{\lambda} + \frac{1}{\lambda} \right]. \quad (143) $$
It follows from (i) that $(i, j)$ (resp. $(j, i)$) is added to $\mathcal{P}C$ only if $\pi^*(i) < \pi^*(j)$ (resp. $\pi^*(i) < \pi^*(j)$). Besides, if

$$ \|M_{i,\cdot} - M_{j,\cdot}\|_2 > 2c_1 \log^{c_2}(nd(\lambda \lor 1)) \left[ \frac{d^{1/6}}{\lambda^{5/6}} \wedge \frac{\sqrt{d}}{\lambda} + \frac{1}{\lambda} \right], \quad (144) $$

then, this implies that $|\bar{P}| \le 1$, otherwise this would contradict Equation (143).

Then, taking a union bound over all possible $(i, j)$, we deduce that there exists an event of probability higher than $1 - cn^2\delta \log^{c'}(nd(\lambda \lor 1))$, such that $\mathcal{P}C$ is consistent and contains all 2-tuples of experts that satisfy (144).

Turning to the estimated permutation $\hat{\pi}_{PC}$, we consider any two experts such that $\pi^*(i) < \pi^*(j)$ and $\hat{\pi}_{PC}(i) > \hat{\pi}_{PC}(j)$. The latter condition implies that $\phi(i) \ge \phi(j)$. Since $\mathcal{P}C$ is consistent, we have $\pi^*(i) \ge 1 + \phi(i)$. Define $\pi^*_-(j)$ as the number of experts $k$ that are below $j$ and are far apart from $j$ in the sense of Equation (144). We know that, under the above event, we have that $\phi(j) \ge \pi^*_-(j)$. This implies that $\pi^*(i) > \pi^*_-(j)$. As a consequence, $i$ and $j$ are not far apart in the sense of Equation (144). This implies that

$$ l_{err}(\hat{\pi}_{PC}, \pi^*) \le 2c_1 \log^{c_2}(nd(\lambda \lor 1)) \left[ \frac{d^{1/6}}{\lambda^{5/6}} \wedge \frac{\sqrt{d}}{\lambda} + \frac{1}{\lambda} \right]. $$

Since $l_{err}(\hat{\pi}_{PC}, \pi^*)$ is equivalent to $l_\infty(\hat{\pi}_{PC}, \pi^*)$, this bound also holds (with a larger constant) for the latter loss. Since $\delta$ has been chosen small enough and since the loss is always smaller than $d$, we arrive at the following risk bound

$$ \mathbb{E}[l_\infty(\hat{\pi}_{PC}, \pi^*)] \le c_1' \log^{c_2'}(nd(\lambda \lor 1)) \left[ \frac{d^{1/6}}{\lambda^{5/6}} \wedge \frac{\sqrt{d}}{\lambda} + \frac{1}{\lambda} \right], $$

which, in turn, implies that

$$ \mathbb{E}[l_\infty(\hat{\pi}_{PC}, \pi^*)] \le c \log^{c'}(nd(\lambda \lor 1)) \left[ \frac{d^{1/6}}{\lambda^{5/6}} \wedge \frac{\sqrt{d}}{\lambda} \right] \wedge d. $$

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

# Appendix J: Proof of the Minimax lower bounds

## J.1. Proof of Theorem 4.1

### J.1.1. Noiseless minimax lower bound

Here, we shall prove the following minimax lower bound holding in the noiseless case $\zeta = 0$.

$$ \mathcal{R}^*[n, d, \lambda, 0] \ge c \left[ \frac{n}{\lambda} e^{-2\lambda} \wedge nd \right] \quad (145) $$

Obviously, the bound remains valid for general $\zeta \ge 0$. Define the positive integer $d_- = 1 \lor [[1/\lambda] \wedge d] \le d$. We build a prior distribution $\nu$ of $M$ as follows. For each row $i = 1, \dots, n$, we sample $W_i \sim \mathcal{B}(1/2)$. If $\zeta_i = 1$, the $i$-th row of $M$ is constant and equal to 1. If $W_i = 0$, then the $i$-th row of $M$ has its $d_-$ first entries equal to 0, while the remaining entries are equal to 1.

We write $\mathbf{P}$ and $\mathbf{E}$ for the corresponding marginal probability and expectations of the data $(x_t, y_t)$.

$$ \mathcal{R}^*[n, d, \lambda, 0] \ge \inf_{\hat{\pi}} \mathbb{E} \left[ \|M_{\hat{\pi}^{-1}} - M_{\pi^{*-1}}\|_2^2 \right]. $$
For each entry $i = 1, \dots, n$, we write $N_i = \sum_t \mathbf{1}_{x_t \in \{i\} \times [d_-]}$ the number of observations on the $d_-$ first columns of the $i$-th row. If $N_i \ge 1$, then the statistician knows the value of $W_i$. Conversely, if $N_i = 0$, then she has no information on the value of $W_i$. Given an estimator $\hat{\pi}$, it is always possible to reduce its loss by ranking at the top the experts such that $N_i \ge 1$ and $W_i = 1$, ranking below the experts such that $N_i \ge 1$ and $W_i = 0$, and putting in between the experts such that $N_i = 0$. Conditionally to the observations $(x_t, y_t)$, the values of $W_i$ such that $N_i = 0$ are still distributed according to a Bernoulli distribution. As a consequence, for any $\hat{\pi}$ which has been rearranged as explained above, the conditional risk satisfies

$$ \mathbf{E} \left[ \| M_{\hat{\pi}^{-1}} - M_{\pi^{*-1}} \|_2^2 | (x_t, y_t) \right] \geq d_- \times g \left( \sum_{i=1}^{n} \mathbf{1}_{N_i=0} \right), $$

where $g(k)$ corresponds to the expected number of error of $\hat{\pi}$ when there are exactly $k$ rows without any observations. Since conditionally to $\hat{\pi}$, the corresponding values of $W$ have been sampled independently as Bernoulli random variables with parameter $1/2$, we arrive at the following expression for $g(k)$:

$$ g(k) = \sum_{i=1}^{k} \mathbb{P}[\{W_i = 1\} \cap \{\sum_{j=1}^{k} W_j \le k - i\}] + \mathbb{P}[\{W_i = 0\} \cap \{\sum_{j=1}^{k} W_j > k - i\}]. $$

We have $g(1) = 0$, $g(2) = 1/2$, $g(3) = 1$. For $k \ge 4$, we focus on the $\lfloor k/4 \rfloor$ first and $\lfloor k/4 \rfloor$ last entries to deduce that

$$ \begin{aligned} g(k) &\ge \mathbb{E} \left[ \sum_{i=1}^{\lfloor k/4 \rfloor} W_i \right] P \left[ \sum_{i=\lfloor k/4 \rfloor+1}^{k} W_i \le k/2 \right] + \mathbb{E} \left[ \sum_{i=k-\lfloor k/4 \rfloor+1}^{k} (1-W_i) \right] P \left[ \sum_{i=1}^{k-\lfloor k/4 \rfloor} (1-W_i) \le k/2 \right] \\ &\ge 0.5 \left[ \frac{k}{4} \right]. \end{aligned} $$

Hence, there exists a universal constant $c > 0$ such that we have $g(k) \ge c(k - 1)$ for any $k \ge 1$. Since $N_i$ follows a Poisson distribution with parameter $\lambda d_-$, $V = \sum_{i=1}^n \mathbf{1}_{N_i=0}$ follows a binomial distribution with parameters $(e^{-\lambda d_-}, n)$. We obtain $\mathcal{R}^*[n, d, \lambda, 0] \ge cd_- \mathbb{E}[(V - 1)_+]$. If $\mathbb{E}[V] \ge 2$, then we simply use $\mathbb{E}[(V - 1)_+] \ge \mathbb{E}[V]/2$. If $\mathbb{E}[V] < 2$, we use $\mathbb{E}[(V - 1)_+] \ge \mathbb{P}[V = 2] = \frac{n(n-1)}{2}e^{-2\lambda d_-}(1 - e^{-2\lambda d_-})^{n-2} \ge c'n^2e^{-2\lambda d_-}$. In any case, we conclude that

$$ \mathcal{R}^*[n, d, \lambda, 0] \ge c'' d_- n e^{-2\lambda d_-}. $$

If $\lambda \le 1/d$, then $d_- = d$, and the right hand-side is higher than $c''nde^{-2}$. If $\lambda \in [1/d, 1]$, then we have $d_- \in [1/(2\lambda), 1/\lambda]$ and the right hand-side risk is higher than $cn/\lambda$. Finally, if $\lambda \ge 1$, we take $d_- = 1$ and the right hand-side is higher than $c'ne^{-2\lambda}$. We have proved Equation (145).

### J.1.2. Proof of the remaining regimes

Since the minimax risk is increasing with $n$ and $d$, we can assume without loss of generality that both $n$ and $d$ express as a power of 2.

We shall first build a collection of prior distributions $\nu_G$ indexed by $G \in \mathcal{G}$ on $M$. We denote $\mathbf{P}_G^{(\text{full})}$ and $\mathbf{E}_G^{(\text{full})}$ the corresponding marginal probability distributions and expectations on the data $(x_t, y_t)$. Since we aim at proving the lower bound in the Gaussian setting, we assume that the data $y_t$ is a normal random variable with mean $M_{x_t}$ and variance $\zeta^2$ conditionally on $M$ and $x_t$. The minimax risk (4) is higher than the worst Bayesian risk.

$$ \mathcal{R}^*[n, d, \lambda, \zeta] \ge \inf_{\hat{\pi}} \sup_{G \in \mathcal{G}} \mathbf{E}_G^{\text{full}} \left[ \| M_{\hat{\pi}^{-1}} - M_{\pi^{*-1}} \|_F^2 \right]. \quad (146) $$

We first spend some time defining the corresponding prior distributions before applying a sequence of reduction arguments.
### J.1.3. Construction of the Prior distribution on M

Let $\tilde{n} \in [n]$ be an a power of 2 so that $n/\tilde{n}$ is an integer. From a broad perspective, the general purpose of this prior construction is to break down the permutation estimation problem into $n/\tilde{n}$ independent bisection problems of size $\tilde{n}$. We will fix the value of $\tilde{n}$ at the end of the proof. The permuted matrix $M_{\pi^{*-1}}$ will turn out to be block constant and we introduce $\tilde{d} \in [d]$ the number of blocks of questions, each of them being of size $d/\tilde{d}$. Here we assume that $\tilde{d}$ is a power of 2 so that $d/\tilde{d}$ is an integer. $\tilde{d}$ will be also fixed at the end of the proof.

We introduce the staircase matrix $C$ of dimension $(n/\tilde{n}) \times \tilde{d}$ such that $C_{\iota, \kappa} = \iota \tilde{n}/(4n) + \kappa/(4\tilde{d})$. Also write $U$ for the constant $\tilde{n} \times d/\tilde{d}$ matrix whose entries are all equal to one. With this notation, the Kronecker product matrix $C \otimes U$ of size $n \times d$ is a bi-isotonic staircase matrix with blocks of size $\tilde{n} \times (d/\tilde{d})$.

Then, we shall perturb the matrix $C \otimes U$ in order to simultaneously craft $n/\tilde{n}$ independent clustering problems of size $\tilde{n}$ each. Set $\tilde{\lambda} = \lambda \frac{d}{\tilde{d}}$ and $\lambda_0 = \tilde{n}\tilde{\lambda}$. Let $v$ be a positive number and let also $q$ be an integer smaller than or equal to $\tilde{d}$ and

$$M = C \otimes U + v \frac{\zeta}{\sqrt{\lambda_0}} B^{(\text{full})}, \quad (147)$$

where the random matrix $B^{(\text{full})} \in \{0, 1\}^{n \times d}$ is defined below.

For this purpose, we consider a collection $\mathcal{G}$ of subsets of $[\tilde{n}]$ with size $\tilde{n}/2$ that are well-separated in symmetric difference as defined by the following lemma.

**Lemma J.1.** There exists a numerical constant $c_0$ such that the following holds for any even integer $\tilde{n}$. There exists a collection $\mathcal{G}$ of subsets of $[\tilde{n}]$ with size $\tilde{n}/2$ whose satisfies $\log(|\mathcal{G}|) \ge c_0|\tilde{n}|$ and whose elements are $\tilde{n}/4$-separated, that is $|G_1\Delta G_2| \ge \tilde{n}/4$ for any $G_1 \neq G_2$.

The above result is a straightforward consequence of Varshamov-Gilbert's lemma – see e.g. [29].

For each block $\iota \in [n/\tilde{n}]$, we fix a subset $G^{(\iota)}$ from $\mathcal{G}$. Then, we consider its 'translation' $G^{t(\iota)} = \{x + (\iota - 1)\tilde{n} : x \in G^{\iota}\}$. The experts of $G^{t(\iota)}$ will correspond to the subgroup of 'higher' experts in the group $\iota$. We write $\mathbf{G} = (G^{t(1)}, \dots, G^{t(n/\tilde{n})})$ and $\mathcal{G}$ the corresponding collection of all possible $\mathbf{G}$. Given any such $\mathbf{G}$, we shall define a prior distribution $\nu_{\mathbf{G}}$ on $M$.

For $\iota \in [n/\tilde{n}]$, we sample uniformly a subset $Q^{(\iota)}$ of $q$ block of questions among the $\tilde{d}$ blocks. In each of these $q$ blocks, the corresponding rows of $B^{(\text{full})}$ are equal to one. More formally, upon writing $\mathbf{1}_{d/\tilde{d}}$ for the constant vector of size $d/\tilde{d}$, we have

$$B^{(\text{full})} = \sum_{\iota=1}^{n/\tilde{n}} \mathbf{1}_{G^{t(\iota)}} (Q^{(\iota)} \otimes \mathbf{1}_{d/\tilde{d}})^T . \quad (148)$$

To sum up, we define a prior distribution $\nu_{\mathbf{G}}$ on $B^{(\text{full})}$ (and equivalently on $M$) such that, under $\nu_{\mathbf{G}}$, all the rows of $B^{(\text{full})}$ that do not belong to any $G^{t(\iota)}$ are zero. All the rows belonging to the same set $G^{t(\iota)}$ are equal and block constants with $\tilde{d}$ blocks of size $d/\tilde{d}$, among which $q$ blocks are exactly equal to one.

Coming back to the matrix $M$ defined in (148), we see that as soon as

$$2v\zeta/\sqrt{\lambda_0} \le \tilde{n}/(4n) \wedge 1/(4\tilde{d}), \quad (149)$$

then, almost surely, the matrix $M$, is up to a (non-unique) permutation, bi-isotonic and its coefficients are in $[0, 1]$. Defining the subset $\overline{G}^{(\iota)} = \{i + (\iota - 1)\tilde{n} : i \in [\tilde{n}]\}$, we see that, under
<figure><img src="image_19.png" /><figcaption>Figure 6: Example of a matrix M sampled from $\nu_G$.</figcaption></figure>

$\nu_G$, recovering a suitable permutation $\pi^*$ is exactly equivalent to estimating the subgroup $G^{t(\iota)} \subset \overline{G}^{(\iota)}$ for each $\iota = 1, \dots, n/\tilde{n}$. This construction of M is illustrated in Figure 6. To sum up, the prior distribution $\nu_G$ on M requires the choice of the parameters $\tilde{n} \in [n]$, $\tilde{d} \in [d]$, the sparsity $q \in [\tilde{d}]$, and some signal level $v > 0$ satisfying (149).

As we shall use several reduction arguments, we need to introduce some new notation. First, we respectively denote $\mathbf{P}_{\mathbf{G}}^{(\text{full})}$ and $\mathbf{E}_{\mathbf{G}}^{(\text{full})}$ for the marginal probability and expectation with respect to the data when M is sampled according to $\nu_G$.

The distribution of the rows $\overline{G}^{(\iota)}$ in M under $\nu_G$ only depends on $G^{(\iota)}$. In what follows, we write $\nu_{G^{(\iota)}}$ for this distribution. Similarly, we write $\mathbf{P}_{G^{(\iota)}}^{(\text{full})}$ for the corresponding marginal distribution of the observations $(x_t, y_t)$ such that $(x_t)_1 \in \overline{G}^{(\iota)}$. By the poissonization trick, the distribution $\mathbf{P}_{\mathbf{G}}^{(\text{full})}$ is a product measure of $\mathbf{P}_{G^{(\iota)}}^{(\text{full})}$ for $\iota = 1, \dots, n/\tilde{n}$. We write $\mathbf{E}_{G^{(\iota)}}^{(\text{full})}$ for the corresponding expectation.

**Step 2: Problem Reduction** We start with prior distributions $\nu_G$.

$$ \mathcal{R}^*[n, d, \lambda, \zeta] \geq \inf_{\hat{\pi}} \sup_{\mathbf{G} \in \mathcal{G}} \mathbb{E}_{\mathbf{G}}^{(\text{full})} \| M_{\pi^{*-1}} - M_{\hat{\pi}^{-1}} \|_2^2 $$

For each of these matrices M sampled from a distribution $\nu_G$, it turns out that $\pi^*(\overline{G}^{(\iota)}) = \overline{G}^{(\iota)}$. Hence, to estimate $\pi^*$, we only need to estimate each $G^{(\iota)} \subset \overline{G}^{(\iota)}$ from the data. Intuitively, we therefore can restrict ourselves to estimators $\hat{\pi}$ satisfying $\hat{\pi}(\overline{G}^{(\iota)}) = \overline{G}^{(\iota)}$. More precisely, if an estimator $\tilde{\pi}$ does not satisfy this condition, then we can modify $\tilde{\pi}$ in $\hat{\pi}$ in order to enforce the $\overline{G}^{(\iota)}$'s to be stable. Since, by Condition (149) experts in different $\overline{G}^{(\iota)}$ are far from each
other, it turns out that the loss of $\hat{\pi}$ is smaller than that of $\tilde{\pi}$.

$$
\begin{align*}
\mathcal{R}^*[n, d, \lambda, \zeta] &\ge \inf_{\hat{\pi}: \hat{\pi}(\bar{G}^{(\ell)}) = \bar{G}^{(\ell)}} \sup_{G \in \mathcal{G}} \sum_{\ell=1}^{n/\tilde{n}} \mathbf{E}_{G^{t(\ell)}}^{(\text{full})} \left[ \| (M_{\hat{\pi}^{-1}} - M_{\pi^{*-1}})_{\bar{G}^{(\ell)}} \|_F^2 \right] \\
&\ge \inf_{\hat{\pi}: \hat{\pi}(\bar{G}^{(\ell)}) = \bar{G}^{(\ell)}} \sum_{\ell=1}^{n/\tilde{n}} \sup_{G^{t(\ell)}} \mathbf{E}_{G^{t(\ell)}}^{(\text{full})} \left[ \| (M_{\hat{\pi}^{-1}} - M_{\pi^{*-1}})_{\bar{G}^{(\ell)}} \|_F^2 \right] \\
&\ge \sum_{\ell=1}^{n/\tilde{n}} \inf_{\hat{\pi}^{(\ell)}} \sup_{G^{t(\ell)}} \mathbf{E}_{G^{t(\ell)}}^{(\text{full})} \left[ \| (M_{\hat{\pi}^{(\ell)-1}} - M_{\pi^{*-1}})_{\bar{G}^{(\ell)}} \|_F^2 \right],
\end{align*}
$$

where, in the last line, $\hat{\pi}^{(\ell)}$ stands for any estimator of the restriction $\pi^*$ to $\bar{G}^{(\ell)}$. By symmetry, we arrive at

$$
\mathcal{R}^*[n, d, \lambda, \zeta] \geq \frac{n}{\tilde{n}} \inf_{\hat{\pi}^{(1)}} \sup_{G^{t(1)}} \mathbf{E}_{G^{t(1)}}^{(\text{full})} \left[ \| (M_{\hat{\pi}^{(1)-1}} - M_{\pi^{*-1}})_{\bar{G}^{(1)}} \|_F^2 \right] \quad (150)
$$

In summary, we have reduced the problem of estimating $\pi^*$ into the sum of $n/\tilde{n}$ problems of size $\tilde{n}$. Under $\nu_{G^{t(\ell)}}$, the restriction of $M$ to $\bar{G}^{(\ell)}$ contains $\tilde{n}/2$ good experts (those in $G^{t(\ell)}$) and $\tilde{n}/2$ bad experts. The square Euclidean distance between these two types of experts is $\frac{q\nu^2 d\zeta^2}{\lambda_0 \tilde{d}}$. If we denote $\hat{G}^{t(\ell)}$ the set of the $\tilde{n}/2$ best experts according to $\hat{\pi}^{(\ell)}$, then the loss writes as

$$
\| (M_{\hat{\pi}^{(\ell)-1}} - M_{\pi^{*-1}})_{\bar{G}^{(\ell)}} \|_F^2 = \frac{q\nu^2 d\zeta^2}{\lambda_0 \tilde{d}} |\hat{G}^{(\ell)} \Delta G^{t(\ell)}| .
$$

Coming back to (150), we obtain

$$
\mathcal{R}^*[n, d, \lambda, \zeta] \geq \frac{nq\nu^2 d\zeta^2}{\tilde{n}\lambda_0\tilde{d}} \inf_{\hat{G}^{(1)}} \sup_{G^{t(1)}} \mathbf{E}_{G^{t(1)}}^{(\text{full})} \left[ |\hat{G}^{(1)} \Delta G^{t(1)}| \right].
$$

Since all possible values of $G^{t(1)}$ are $\tilde{n}/4$-apart by definition of the collection $\mathcal{G}$, we deduce that

$$
\mathcal{R}^*[n, d, \lambda, \zeta] \geq \frac{nq\nu^2 d\zeta^2}{8\lambda_0 \tilde{d}} \inf_{\hat{G}^{(1)}} \sup_{G^{t(1)}} \mathbf{P}_{G^{t(1)}}^{(\text{full})} [\hat{G}^{(1)} \neq G^{t(1)}] .
$$

For any group $G^{t(1)}$, under $\nu_{G^{t(1)}}$, the rows of the restrictions of $M$ to $\bar{G}^{t(1)}$ are block-constant with $\tilde{d}$ blocks of $d/\tilde{d}$ questions. Consider the $\tilde{n} \times \tilde{d}$ matrices $N$ and $Y^\downarrow$ defined by

$$
N_{i,j} = \sum_t \mathbf{1}_{x_t \in \{i\} \times [(j-1)(d/\tilde{d})+1, j(d/\tilde{d})+1]} ; \quad Y_{i,j}^\downarrow = \sum_t \mathbf{1}_{x_t \in \{i\} \times [(j-1)(d/\tilde{d})+1, j(d/\tilde{d})+1]} \left( y_t - \frac{\tilde{n}}{4n} - \frac{j}{4\tilde{d}} \right) .
$$

To simplify the notation, we write henceforth $G$ and $\hat{G}$ for $G^{t(1)}$ and $\hat{G}^{(1)}$ respectively. We also write $\mathbf{P}_G$ for the corresponding marginal distribution of $N$ and $Y^\downarrow$. By a sufficiency argument, it turns out that

$$
\inf_{\hat{G} \quad G} \sup \mathbf{P}_G^{(\text{full})} [\hat{G} \neq G] = \inf_{\hat{G} \quad G} \sup \mathbf{P}_G [\hat{G} \neq G] .
$$

Hence, we arrive at the following conclusion

$$
\mathcal{R}^*[n, d, \lambda, \zeta] \geq \frac{nq\nu^2 d\zeta^2}{8\lambda_0 \tilde{d}} \inf_{\hat{G} \quad G} \sup_{G} \mathbf{P}_G [\hat{G} \neq G] . \quad (151)
$$

Let us introduce a third-part distribution $\mathbf{P}_0$ on $N$ and $Y^\downarrow$ corresponding to the case $\nu = 0$. Each of the entry of $N$ therefore follows an independent Poisson distribution with parameter $\tilde{\lambda}$ and, given $N_{i,j}$, we have $Y^\downarrow \sim \mathcal{N}(0, N_{i,j}\zeta^2)$. We then deduce from Fano's inequality [29] that

$$
\inf_{\hat{G} \quad G \in \mathcal{G}} \sup \mathbf{P}_G (\hat{G} \neq G) \geq 1 - \frac{1 + \max_{G \in \mathcal{G}} \text{KL}(\mathbf{P}_G \| \mathbf{P}_0)}{\log(|\mathcal{G}|)}, \quad (152)
$$
where KL(·||·) stands for the Kullback-Leibler divergence. Then, the following lemma bounds these Kullback-Leibler divergences.

**Lemma J.2.** Assume that $\lambda_0 = \tilde{n}\lambda d/\tilde{d} \ge 1$ and that $8v^2 \le 1$. For any $G \in \mathcal{G}$, we have

$$KL(\mathbf{P}_G \| \mathbf{P}_0) \le \frac{4v^2q^2}{\tilde{d}}.$$

In the specific case where $\tilde{d} = q = 1$, we have $KL(\mathbf{P}_G \| \mathbf{P}_0) = v^2/2$ for any $G \in \mathcal{G}$, any $\lambda_0 > 0$, and any $v > 0$.

Let us summarize our findings by combining (151), (152), with Lemma J.2 and the different constraints on the parameters (149).

**Proposition J.3.** Provided that $\tilde{n}$, $\tilde{d}$, $q$, and $v$ satisfy the two following conditions

$$\lambda \ge \frac{\tilde{d}}{\tilde{n}d}; \qquad (153)$$

$$v \le 2^{-3/2} \wedge \left[ c_0 \frac{\sqrt{\tilde{d}\tilde{n}}}{q} \wedge c_1 \frac{\sqrt{\lambda}}{\zeta} \left[ \frac{\tilde{n}^{3/2} d^{1/2}}{n\tilde{d}^{1/2}} \wedge \frac{\sqrt{\tilde{n}d}}{\tilde{d}^{3/2}} \right] \right], \qquad (154)$$

then, we have

$$\mathcal{R}^*[n, d, \lambda, \zeta] \ge c'' \frac{nqv^2\zeta^2}{\tilde{n}\lambda}. \qquad (155)$$

In the specific case where we fix $\tilde{d} = q = 1$ and $\tilde{n} = n$, we can deduce from combining (151), (152), and the second part of Lemma J.2 that

$$\mathcal{R}^*[n, d, \lambda, \zeta] \ge c'' \frac{n v^2 \zeta^2}{\tilde{n} \lambda},$$

provided that $v^2 \le c' \frac{\lambda n d}{\zeta^2} \wedge n$. By choosing $v^2$ of the order of the right-hand side, we then deduce that

$$\mathcal{R}^*[n, d, \zeta] \ge c \left[ \frac{n\zeta^2}{\lambda} \wedge nd \right]. \qquad (156)$$

### J.1.4. Step 3. Choice of the parameters and conclusion

Writing $\lambda' = \lambda/\zeta^2$, recall that we aim at proving that

$$R[n, d, \lambda, \zeta] \ge c \left[ \left[ \frac{nd^{1/6}}{\lambda'^{5/6}} \wedge \frac{n^{3/4}d^{1/4}}{\lambda'^{3/4}} \wedge \frac{n^{2/3}\sqrt{d}}{\lambda'^{5/6}} \wedge \frac{n\sqrt{d}}{\lambda'} \right] + \frac{n}{\lambda'} + \frac{n}{\lambda}e^{-2\lambda} \right] \wedge nd. \qquad (157)$$

Since we have proved the lower bound (145) and (156), we only have to prove the corresponding minimax lower bound for the remaining four rates. For this purpose, we shall fix the values of $\tilde{n}$, $\tilde{d}$, $q$, and $v$ and apply from Proposition J.3. In the sequel we write $[x]_{dya}$ for $2^{\log_2(x)}$.

**Case 1:** Rate $\frac{nd^{1/6}}{\lambda'^{5/6}}$. This rate can only occur if $n \le d$, $\lambda' \in [n^3/d, d^2]$ and $\lambda \ge 1 \wedge [\lambda'^{5/6}/d^{1/6}]$. In this case, we take $\tilde{n} = 2$, $\tilde{d} = [(\lambda' d)^{1/3}]_{dya}$, and $q = [\sqrt{\tilde{d}}]$. One readily checks that the conditions (153) and (154) are satisfied for a universal numerical value of $v$. Then, Proposition J.3 leads to the desired rate.

**Case 2:** Rate $\frac{n^{3/4}d^{1/4}}{\lambda'^{3/4}}$. This rate can only occur if $\lambda \ge [1 \wedge (n\lambda'^3/d)^{1/4}]$ and (a) either $n \le d$ and $\lambda' \in [\frac{n}{d}, \frac{n^3}{d}]$ or (b) $n \in [d; d^2]$ and $\lambda' \in [\frac{n}{d}, \frac{d^3}{n}]$. In this case, we take $\tilde{d} = [(\lambda'nd)^{1/4}]_{dya}$,
$\tilde{n} = [n/\tilde{d}]_{dya}$, and $q = [\sqrt{\tilde{n}\tilde{d}}]$. One readily checks that the conditions (153) and (154) are satisfied for an universal numerical value of $v$. Then, Proposition J.3 leads to the desired rate.

**Case 3:** Rate $\frac{n^{2/3}\sqrt{d}}{\lambda^{5/6}}$. This rate can only occur if $\lambda \ge [1 \wedge \frac{\lambda^{5/6}n^{1/3}}{\sqrt{d}}]$ and (a) either $n \in [d, d^2]$ and $\lambda' \in [\frac{d^3}{n}, n^2]$ or (b) $n \ge d^2$ and $\lambda' \in [\frac{n^2}{d^3}, n^2]$. In this case, we take $\tilde{n} = [(n^2/\lambda')^{1/3}]_{dya}$, $\tilde{d} = d$, and $q = [\sqrt{\tilde{n}\tilde{d}}]$. One readily checks that the conditions (153) and (154) are satisfied for an universal numerical value of $v$. Then, Proposition J.3 leads to the desired rate.

**Case 4:** Rate $\frac{n\sqrt{d}}{\lambda'}$. This rate can only occur if $\lambda \ge 1$ and $\lambda' \ge (n \vee d)^2$. In this case, we take $\tilde{n} = 2$, $\tilde{d} = d$, and $q = [\sqrt{\tilde{d}}]$. One readily checks that the conditions (153) and (154) are satisfied for a universal numerical value of $v$. Then, Proposition J.3 leads to the desired rate. This concludes the proof.

### J.1.5. Proof of Lemma J.2

*Proof of Lemma J.2.* In order to bound the Kullback-Leibler discrepancy $KL(P_G||P_0)$, we first observe that the rows of $N$ and $Y^\downarrow$ outside $G$ have the same distribution on $P_G$ and $P_0$. Besides, all the rows of $N$ and $Y^\downarrow$ in $G$ are identically distributed on $P_G$ and on $P_0$. Define the vectors $\overline{N}$ and $\overline{Y}^\downarrow$ by $\overline{N}_j = \zeta^{-1} \sum_{i \in G} N_{i,j}$ and $Y_j^\downarrow = \zeta^{-1} \sum_{i \in G} Y_{i,j}^\downarrow$ are a sufficient statistic for deciphering $P_G$ and $P_0$, we have $KL(P_G||P_0) = KL(P'||P)$ where $P'$ and $P$ stand for the corresponding marginal distributions of $\overline{N}$ and $\overline{Y}^\downarrow$.

Set $u = v/\sqrt{\lambda_0}$. Under $P$, given $\overline{N}$, the $\overline{Y}_j^\downarrow$'s are independent and satisfy $\overline{Y}_j^\downarrow \sim \mathcal{N}(0, \overline{N}_j)$. Under $P'$, conditionally to the subset $Q$ of size $q$ and conditionally to $\overline{N}$, the $\overline{Y}_j^\downarrow$'s are independent and satisfy $\overline{Y}_j^\downarrow \sim \mathcal{N}(u\overline{N}_j1\{j \in Q\}, \overline{N}_j)$.

In the specific case of $q = \tilde{d} = 1$, we can explicitely compute the Kullback Leibler divergence. Conditionally to $\overline{N}_1 = x$, $\overline{Y}^\downarrow$ is either distributed $\mathcal{N}(0, x)$ under $P$ and $\mathcal{N}(ux, x)$ under $P'$. Hence, their conditional Kullback-divergence is $u^2x/2$. Integrating with respect to $x$, we conclude that

$$KL(P' || P) = E \left[ \frac{u^2 \overline{N}}{2} \right] = \frac{u^2 \lambda_0}{2} = \frac{v^2}{2}.$$

We have shown the second result.

Let us come back to the general case. For $z = 1, 0$, define

$$\alpha_z(x, y) = \frac{\lambda_0^x e^{-\lambda_0}}{x!} \frac{1}{\sqrt{2\alpha x}} \exp\left(-\frac{(y - u x z)^2}{2x}\right).$$

Then, the density of $P$ with respect to $\mu \otimes \lambda$ where $\mu$ is the discrete measure and $\lambda$ is the Lebesgues measure is $\prod_j \alpha_0(\overline{N}_j, \overline{Y}_j^\downarrow)$. Besides, the density of $P'$ is

$$\int [\prod_j \alpha_{1_{j \in Q}}(\overline{N}_j, \overline{Y}_j^\downarrow)] d\eta(Q),$$

where $\eta$ stands for the uniform distribution over $\{Q \in \{0, 1\}^\tilde{d} : \|Q\|_0 = q\}$. It is more convenient to first control the $\chi^2$ distance $P$ and $P'$. Since this distance is, up to an additive term of order
1, the second moment of the likelihood ratio between $\mathbf{P}$ and $\mathbf{P}'$, we arrive at the following

$$ 
\begin{aligned}
& \chi^2(\mathbf{P}', \mathbf{P}) + 1 \\
& = \int \left[ \prod_{j \in \tilde{Q} \cap Q'} \frac{[\alpha_1(x_j, y_j)]^2}{\alpha_0(x_j, y_j)} d\mu(x_j) dy_j \right] \left[ \prod_{j \in \tilde{Q} \cap \Delta Q'} \alpha_1(x_j, y_j) d\mu(x_j) dy_j \right] d\eta(Q) d\eta(Q') \\
& = \int \left[ \prod_{j \in \tilde{Q} \cap Q'} \frac{[\alpha_1(x_j, y_j)]^2}{\alpha_0(x_j, y_j)} d\mu(x_j) dy_j \right] d\eta(Q) d\eta(Q') ,
\end{aligned}
$$

since $\alpha_1$ is a density. Let us work out each of these ratios.

$$ 
\begin{aligned}
\int \frac{\alpha_1^2(x, y)}{\alpha_0(x, y)} dxdy &= \int \alpha_0(x, y) \exp\left[\frac{2yux - u^2x^2}{x}\right] d\mu(x)dy \\
&= \sum_{x=0}^{\infty} \frac{\lambda_0^x e^{-\lambda_0}}{x!} e^{u^2x} = \exp(\lambda_0(e^{u^2} - 1)) := \exp(\mathcal{I}) .
\end{aligned}
$$

Coming back to the $\chi^2$ distance, we arrive at the following equality

$$ \chi^2(\mathbf{P}', \mathbf{P}) = \int \exp(\mathcal{I}|Q \cap Q'|) d\eta(Q) d\eta(Q') - 1 . $$

Here, $|Q \cap Q'|$ is distributed as an Hypergeometric distribution with parameters $\tilde{d}$, $q$, and $q/\tilde{d}$. We know from Aldous (p.173) [1] that $|Q \cap Q'|$ follows the same distribution as the random variable $\mathbb{E}(W|\mathcal{B})$ where $W$ is a binomial random variable of parameters $q$, $q/\tilde{d}$ and $\mathcal{B}$ is some suitable $\sigma$-algebra. By Jensen's inequality, we deduce that

$$ \chi^2(\mathbf{P}', \mathbf{P}) \le \mathbb{E}[\exp(\mathcal{I}W)] - 1 = \left[1 + \frac{q}{\tilde{d}}(\exp(\mathcal{I}) - 1)\right]^q - 1 . $$

Recall that $\lambda_0 u^2 = v^2 \le 1/8$. Hence, provided that $\lambda_0 = \tilde{n}\lambda d/\tilde{d} \ge 1$, we have $\mathcal{I} \le 2\lambda_0 u^2 = 2v^2$. It then follows that

$$ \chi^2(\mathbf{P}', \mathbf{P}) \le \exp\left(q^2/\tilde{d}(\exp(\mathcal{I}) - 1)\right) - 1 \le \exp\left(4v^2q^2/\tilde{d}\right) - 1. $$

To conclude, we use the classical bound $\mathrm{KL}(\mathbf{P}'\|\mathbf{P}) \le \log(1 + \chi^2(\mathbf{P}', \mathbf{P}))$ –see e.g. [29]. This leads us to

$$ \mathrm{KL}(\mathbf{P}'\|\mathbf{P}) \le \frac{4v^2q^2}{\tilde{d}} . $$

□

## J.2. Proof of Theorem 2.1

Fix $n$, $d$, $\zeta$, and $\kappa \ge 2$, and assume that, for some $c'$, there exists an estimator $\hat{\pi}$ satisfying

$$ \sup_{\pi^* \in \Pi_n} \sup_{M: M_{\pi^{*-1}} \in \mathcal{C}_{\mathrm{BISO}}} \mathbb{E}_{(\pi^*, M)} \|M_{\hat{\pi}^{-1}} - M_{\pi^{*-1}}\|_F^2 \le c' [\log^{-\kappa}(nd/\zeta_-) \mathcal{R}_F[n, d, \zeta] \wedge nd] , \quad (158) $$

with $\Upsilon = [\log^\kappa(nd/\zeta_-)]$ samples.

Let us show that this bound would contradict the minimax lower bound in the Poisson setting. Fix $\lambda = \frac{112}{3} \log^\kappa(nd/\zeta_-)$ and consider the model (2). Define the estimator $\tilde{\pi}$ such that $\tilde{\pi} = \hat{\pi}$ under the event $\mathcal{A}$ such that there are at least $\Upsilon$ observations on each entry and $\tilde{\pi}$ is computed arbitrarily otherwise. By (158), $\tilde{\pi}$ satisfies

$$ \mathbb{E}_{(\pi^*, M)} \|M_{\hat{\pi}^{-1}} - M_{\pi^{*-1}}\|_F^2 \le nd\mathbb{P}[\mathcal{A}^c] + c' [\log^{-\kappa}(nd/\zeta_-) \mathcal{R}_F[n, d, \zeta] \wedge nd] . \quad (159) $$
By Chernoff' inequality for Poisson random variable, we deduce that

$$ \mathbb{P}[\mathcal{A}^c] \le nd \exp\left[-\frac{3}{28}\lambda\right] \le nd e^{-4\log^\kappa(\mathrm{nd}/\zeta_-)} \le \frac{\zeta_-^2}{nd} e^{-4\log^\kappa(\mathrm{nd}/\zeta_-)+2\log(\mathrm{nd}/\zeta_-)} $$

There exists a constant $c_0$ such that for any $\kappa \ge 2$, $e^{-4x^\kappa+2x} \le \frac{c_0}{x^{2\kappa}}$. We deduce that

$$ \mathbb{P}[\mathcal{A}^c] \le \frac{\zeta_-^2}{nd} \frac{c_0}{\log^{2\kappa}(\mathrm{nd}/\zeta_-)}, $$

where we used that $e^x \ge 1+x^\beta/\beta$ for any $x \ge 0$ and any $\beta > 0$ and that $\kappa \ge 2$. We then deduce from (159) that

$$ \mathbb{E}_{(\pi^*, M)} \| M_{\hat{\pi}-1} - M_{\pi^{*-1}} \|_F^2 \le \left( c' + \frac{c_0}{\log^\kappa(\mathrm{nd}/\zeta_-)} \right) \left[ \log^{-\kappa}(\mathrm{nd}/\zeta_-) \mathcal{R}_F[n, d, \zeta] \wedge nd \right] . \quad (160) $$

For $\lambda \ge 1$, $\mathcal{R}_F[n, d, \zeta/\sqrt{\lambda}] \ge \frac{\mathcal{R}_F[n, d, \zeta]}{\lambda}$. We deduce that

$$ \mathbb{E}_{(\pi^*, M)} \| M_{\hat{\pi}-1} - M_{\pi^{*-1}} \|_F^2 \le \frac{112}{3} \left( c' + \frac{c_0}{\log^\kappa(\mathrm{nd}/\zeta_-)} \right) \left[ \mathcal{R}_F[n, d, \zeta/\sqrt{\lambda}] \wedge nd \right] . $$

Taking $c'$ small enough compared to the numerical constant $c$ in Theorem 4.1 contradicts this last theorem provided that $\mathrm{nd}/\zeta_-$ is larger than some some numerical constant. Hence, no estimator can achieve (158) for this constant $c'$ when $(\mathrm{nd}/\zeta_-)$ is large enough.

It remains to consider the case where $\mathrm{nd}/\zeta_-$ is smaller than some constant $c'' \ge 2$. We only need to prove that the minimax risk is lower bounded by $c_0/\sqrt{\lambda}$ where $\Upsilon$ is the sample size. Since the minimax risk is non-decreasing with respect to $n$, $d$, and $\zeta$, we only have to consider the case $n=2$, $d=1$, $\zeta=2/c''$. Define $a = \zeta/\sqrt{\Upsilon}$. Consider a problem where either $M = (a, 0)^T$ or $M = (0, a)^T$. Then, with positive probability, no test is able to distinguish both hypotheses and the risk of any estimator is at most of the order $a^2 = \zeta^2/\Upsilon$. The result follows.

## References

[1] D. J. Aldous. Exchangeability and related topics, École d'été de probabilités de Saint Flour XIII, volume 1117 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1985.

[2] T. P. Ballinger and N. T. Wilcox. Decisions, error and heterogeneity. The Economic Journal, 107(443):1090–1105, 1997.

[3] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities. Oxford University Press, Oxford, 2013. A nonasymptotic theory of independence, With a foreword by Michel Ledoux.

[4] R. A. Bradley and M. E. Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324–345, 1952.

[5] M. Braverman and E. Mossel. Noisy sorting without resampling. In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 268–276, 2008.

[6] S. Chatterjee. Matrix estimation by universal singular value thresholding. The Annals of Statistics, 43(1):177–214, 2015.

[7] S. Chatterjee, A. Guntuboyina, and B. Sen. On matrix estimation under monotonicity constraints. Bernoulli, 24(2):1072–1100, 2018.

[8] S. Chatterjee and S. Mukherjee. Estimation in tournaments and graphs under monotonicity constraints. IEEE Transactions on Information Theory, 65(6):3525–3539, 2019.
[9] P. Chen, C. Gao, and A. Y. Zhang. Optimal full ranking from pairwise comparisons. arXiv preprint arXiv:2101.08421, 2021.

[10] Y. Chen, J. Fan, C. Ma, and K. Wang. Spectral method and regularized mle are both optimal for top-k ranking. Annals of statistics, 47(4):2204, 2019.

[11] A. P. Dawid and A. M. Skene. Maximum likelihood estimation of observer error-rates using the em algorithm. Journal of the Royal Statistical Society: Series C (Applied Statistics), 28(1):20–28, 1979.

[12] N. Flammarion, C. Mao, and P. Rigollet. Optimal rates of statistical seriation. Bernoulli, 25(1):623–653, 2019.

[13] R. Kyng, A. Rao, and S. Sachdeva. Fast, provable algorithms for isotonic regression in all 1_p-norms. Advances in neural information processing systems, 28, 2015.

[14] A. Liu and A. Moitra. Better algorithms for estimating non-parametric models in crowdsourcing and rank aggregation. In Conference on Learning Theory, pages 2780–2829. PMLR, 2020.

[15] H. Liu, C. Gao, and R. J. Samworth. Minimax rates in sparse, high-dimensional change-point detection. arXiv preprint arXiv:1907.10012, 2019.

[16] R. D. Luce. Individual choice behavior: A theoretical analysis. Courier Corporation, 2012.

[17] C. Mao, A. Pananjady, and M. J. Wainwright. Towards optimal estimation of bivariate isotonic matrices with unknown permutations. The Annals of Statistics, 48(6):3183–3205, 2020.

[18] C. Mao, J. Weed, and P. Rigollet. Minimax rates and efficient algorithms for noisy sorting. In Algorithmic Learning Theory, pages 821–847. PMLR, 2018.

[19] D. H. McLaughlin and R. D. Luce. Stochastic transitivity and cancellation of preferences between bitter-sweet solutions. Psychonomic Science, 2(1):89–90, 1965.

[20] A. Pananjady, C. Mao, V. Muthukumar, M. J. Wainwright, and T. A. Courtade. Worst-case versus average-case design for estimation from partial pairwise comparisons. The Annals of Statistics, 48(2):1072–1097, 2020.

[21] A. Pananjady and R. J. Samworth. Isotonic regression with unknown permutations: Statistics, computation and adaptation. The Annals of Statistics, 50(1):324–350, 2022.

[22] D. Pollard. Lecture notes. 2016.

[23] M. Rudelson and R. Vershynin. Hanson-wright inequality and sub-gaussian concentration. Electronic Communications in Probability, 18, 2013.

[24] N. Shah, S. Balakrishnan, J. Bradley, A. Parekh, K. Ramchandran, and M. Wainwright. Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence. In Artificial intelligence and statistics, pages 856–865. PMLR, 2015.

[25] N. B. Shah, S. Balakrishnan, A. Guntuboyina, and M. J. Wainwright. Stochastically transitive models for pairwise comparisons: Statistical and computational issues. IEEE Transactions on Information Theory, 63(2):934–959, 2016.

[26] N. B. Shah, S. Balakrishnan, and M. J. Wainwright. Feeling the bern: Adaptive estimators for bernoulli probabilities of pairwise comparisons. IEEE Transactions on Information Theory, 65(8):4854–4874, 2019.

[27] N. B. Shah, S. Balakrishnan, and M. J. Wainwright. A permutation-based model for crowd labeling: Optimal estimation and robustness. IEEE Transactions on Information Theory, 67(6):4162–4184, 2020.

[28] L. Thurstone. A law of comparative judgment. Psychological Review, 34(4), 1927.

[29] A. B. Tsybakov. Introduction to Nonparametric Estimation. 2008.

[30] R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.

[31] S. Vigna. Spectral ranking. Network Science, 4(4):433–445, 2016.

[32] M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48.
Cambridge University Press, 2019.

[33] Y. Wu. Lecture notes on information-theoretic methods for high-dimensional statistics. Lecture Notes for ECE598YW (UIUC), 16, 2017.

[34] A. R. Zhang, T. T. Cai, and Y. Wu. Heteroskedastic pca: Algorithm, optimality, and applications. The Annals of Statistics, 50(1):53–80, 2022.