# Minimax optimal submatrix detection: Sharp non-asymptotic rates

arXiv: https://arxiv.org/abs/2605.09569 · HTML: https://mlsanity.com/paper/2605.09569/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 51 references that are in the map.
- First posted on arXiv 10 May 2026.

## Abstract (arXiv)

Given an observation mathbf Y ∈ ℝd1× d2 from the model mathbf Y = mathbf X + mathbf E where mathbf X is constant and mathbf E has i.i.d. N(0,1) entries, we consider the problem of detecting a planted submatrix in the mean matrix mathbf X. Specifically, we aim to distinguish the null hypothesis mathbf X = 0 from the alternative hypothesis in which mathbf X is non-zero only on a submatrix of size s1 × s2 with elevated entries bounded below by μ>0. We establish a minimax lower bound characterizing how large μ must be to ensure that the two hypotheses are distinguishable with high probability. Furthermore, we derive novel minimax-optimal tests achieving the lower bound, and describe extensions of these tests that are adaptive to unknown sparsity levels s1 and s2. In contrast with previous work, which required restrictive assumptions on s1,s2, d1 and d2, our non-asymptotic upper and lower bounds match for any configuration of these parameters.