ith probability at least $1 - d^{-3}$, we have, $$\begin{aligned}
 \label{eq:topl_error}
{\|M - \E[M]\|} \leq 22e^{b}\sqrt{\frac{\log d}{\beta d} \sum_{j=1}^n \ell_j} +\frac{64 \log d}{3} \leq 32e^{b}\sqrt{\frac{\log d}{\beta d}\sum_{j=1}^n \ell_j} \;,\end{aligned}$$ where the second inequality follows from the assumption that $\sum_{j = 1}^n \ell_j \geq 2^{12} d\log d$ and $\beta \leq 1$.

### Proof of Lemma \[lem:prob\_toplbound\]

Define $i_{\min} \equiv \arg \min_{i \in S} \theta_i$. We claim the following. For all $i \in S$ and any $1 \leq \ell \leq |S|-1$, $$\begin{aligned}
 \label{eq:prob_topl_eq}
\mathbb{P}[\sigma^{-1}(i) > \ell] \;\leq\; \mathbb{P}[\sigma^{-1}(i_{\min}) > \ell] \;\; \text{and} \;\; \mathbb{P}[\sigma^{-1}(i_{\min}) = \ell]  \; \geq \; \mathbb{P}[\sigma^{-1}(i_{\min}) = 1]\,.\end{aligned}$$ Therefore $\mathbb{P}[\sigma^{-1}(i) \leq \ell] \;\geq\; \mathbb{P}[\sigma^{-1}(i_{\min}) \leq \ell]$. Using $\mathbb{P}[\sigma^{-1}(i_{\min}) = 1] > e^{-2b}/\kappa$, we get the desired bound $\mathbb{P}[\sigma^{-1}(i) \leq \ell] >  e^{-2b} \ell/\kappa$.

To prove the claim , let $\widehat{\sigma}_1^\ell$ denote a ranking of top-$\ell$ items of the set $S$ and $\P[\widehat{\sigma}_1^\ell]$ be the probability of observing $\widehat{\sigma}_1^\ell$. Let ${i \in (\widehat{\sigma}_1^\ell)^{-1}}$ denote that $i = (\widehat{\sigma}_1^\ell)^{-1}(j)$ for some $1 \leq j \leq \ell$. Let $$\begin{aligned}
\Omega_1 = \Big\{ \widehat{\sigma}_1^\ell : {i \notin (\widehat{\sigma}_1^\ell)^{-1}}, {i_{\min} \in (\widehat{\sigma}_1^\ell)^{-1}} \Big\} \;\; \text{and} \;\; \Omega_2 = \Big\{ \widehat{\sigma}_1^\ell : {i \in (\widehat{\sigma}_1^\ell)^{-1}}, {i_{\min} \notin (\widehat{\sigma}_1^\ell)^{-1}} \Big\}.\end{aligned}$$ We have $\mathbb{P}[\sigma^{-1}(i) > \ell]  - \mathbb{P}[\sigma^{-1}(i_{\min}) > \ell] =  \sum_{\widehat{\sigma}_1^\ell \in \Omega_1}\P[\widehat{\sigma}_1^\ell] -   \sum_{\widehat{\sigma}_1^\ell \in \Omega_2} \P[\widehat{\sigma}_1^\ell].$ Now, take any ranking $\widehat{\sigma}_1^\ell \in \Omega_1$ and