Minimax estimation of topic distributions with weak sparsity

Fix an integer $K \ge 2$, $q \in (0, 1)$ and constants $c, \kappa > 0$. One observes independent word-count vectors $$X_i \sim \operatorname{Multinomial}(N, A w_i), \qquad i = 1, \dots, n,$$ where $N \ge 2$, $A \in [0,1]^{p \times K}$ and $W = (w_1, \dots, w_n) \in [0,1]^{K \times n}$, and every column of $A$ and of $W$ sums to one. Both matrices are unknown; $K$ is known and fixed. Let $\mathcal{F}_{n,N,p}(q, s; c, \kappa)$ be the set of pairs $(A, W)$ such that $$\sigma_K(A) \ge c\sqrt{K}, \qquad \lambda_{\min}(W W^{\mathsf T}/n) \ge c, \qquad \min_{k,l} (A^{\mathsf T} A)_{kl} \ge c,$$ where $\sigma_K$ is the smallest of the $K$ singular values; such that every topic $k$ has an anchor word $j_k$, with $A_{j_k k} > 0$ and $A_{j_k l} = 0$ for $l \ne k$, whose average corpus frequency satisfies $$\mu_{j_k} := \frac{1}{n} \sum_{i=1}^{n} (A W)_{j_k i} > \kappa \sqrt{\frac{\log(p \vee n)}{nN}};$$ and such that, writing the entries of each column in decreasing order as $A_{(1)k} \ge \cdots \ge A_{(p)k}$, $$\max_{k \le K} \max_{j \le p} \, j \, A_{(j)k}^{\,q} \le s.$$ This weak sparsity condition bounds the decay of the ordered entries, not the number of nonzero entries or $\sum_j A_{jk}^q$, and allows arbitrarily many small positive entries. Tran, Liu and Donnat introduced it and gave a thresholded spectral estimator $\widehat{A}$ which, under these conditions with a large enough anchor threshold, a stability condition on the vertex-hunting step it uses, and $s \bigl(\log(p \vee n)/(nN)\bigr)^{(1-q)/2} \to 0$, satisfies with probability $1 - o\bigl((p \vee n)^{-1}\bigr)$ $$\|\widehat{A} - A\|_1 \le C \left[ \left( \frac{\log(p \vee n)}{nN} \right)^{1/4} + s \left( \frac{\log(p \vee n)}{nN} \right)^{(1-q)/2} \right],$$ with $C$ depending on $K$ and $q$. For an elementwise sparse $A$, Bing, Bunea and Wegkamp proved a minimax lower bound and an upper bound, in terms of the number of nonzero entries of $A$, that matches it up to a logarithmic factor in many regimes; without sparsity, Ke and Wang established the rate $\sqrt{p/(nN)}$ for this loss under conditions on $n$, $N$ and $p$.

Problem. Determine, up to multiplicative constants independent of $n$, $N$, $p$ and $s$, the minimax risk $$R^*_{n,N,p}(q, s; c, \kappa) = \inf_{\widehat{A}} \sup_{(A, W) \in \mathcal{F}_{n,N,p}(q, s; c, \kappa)} \mathbb{E}_{A,W} \left[ \min_{\pi \in S_K} \sum_{k=1}^{K} \sum_{j=1}^{p} \bigl| \widehat{A}_{jk} - A_{j, \pi(k)} \bigr| \right],$$ the infimum taken over measurable estimators whose columns are probability vectors. Consider the parameter regimes in which the class is nonempty, with $K, q, c, \kappa$ fixed and $\kappa$ sufficiently large as in the anchor frequency condition of Tran, Liu and Donnat, and establish matching upper and lower bounds, with the correct dependence on $s$ and any necessary logarithmic factors as the vocabulary size grows. The constants may depend on the fixed parameters.