Sharp minimax risks and phase transitions in sparse submatrix detection
Abstract
In this paper, we study the minimax risk of detecting a sparse, elevated-mean Gaussian submatrix planted in a larger noisy matrix. When the planted submatrix has size n× n and the ambient matrix has size N× N with N=n1+α, the seminal work of Butucea and Ingster (2013) identifies the sharp detection boundary around which the risk converges to $0$ or $1$. We extend that zero-one theory by determining sharp risk asymptotics throughout a two-parameter phase diagram. Above the boundary, the risk decays stretched- or super-exponentially fast, and we determine its precise exponent. Below the boundary, where the risk tends to $1$, we obtain matching absolute-constant bounds for its polynomial rate of convergence. In both regimes, the asymptotics change across the line α+δ=1/2, where δ parametrizes the signed distance from the detection boundary. Finally, on the boundary, we show that the minimax risk converges to the nondegenerate constant 1/2 in a very sparse regime where n remains fixed and N→∞. Each of these rates corresponds to the risk of a suitably calibrated scan or sum test, whence follow the upper bounds. The main problem is to derive the matching regime-specific lower bounds. The mixture likelihood ratio is an average rather than a product and thus its logarithm lacks the additive structure required by standard large deviation formulations. On the other hand, classical second-moment estimates fail to be sharp due to overlap-induced correlations. To address these issues, we develop two general lower-bound principles based on truncated mixture likelihoods, tailored to the target risks on both sides of the detection boundary. The same framework yields sharp risk asymptotics for sparse subtensors with equal side lengths and also applies to more general testing problems including the detection of rectangular subtensors.
Related
- Minimax and Adaptive Transfer Learning for Sparse Canonical Correlation Analysis
- Sharp Minimax Gram-Determinant Asymptotics for Labelled Unit Decompositions of the Identity and Recent Developments on Makai's Conjecture
- Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits
- Sharp Critical Minimax Laws and No-Learning Thresholds in Continuous-Time Adaptive Control
- Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models
BibTeX
@misc{goswami2026sharp,
title = {{Sharp minimax risks and phase transitions in sparse submatrix detection}},
author = {Subhajit Goswami and Rajarshi Mukherjee},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.31583},
eprint = {2605.31583},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.31583},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp minimax risks and phase transitions in sparse submatrix detection
AU - Subhajit Goswami
AU - Rajarshi Mukherjee
PY - 2026
DA - 2026/10/24
PB - arXiv
DO - 10.48550/arxiv.2605.31583
UR - https://arxiv.org/abs/2605.31583
AB - In this paper, we study the minimax risk of detecting a sparse, elevated-mean Gaussian submatrix planted in a larger noisy matrix. When the planted submatrix has size n× n and the ambient matrix has size N× N with N=n^1+α, the seminal work of Butucea and Ingster (2013) identifies the sharp detection boundary around which the risk converges to $0$ or $1$. We extend that zero-one theory by determining sharp risk asymptotics throughout a two-parameter phase diagram. Above the boundary, the risk decays stretched- or super-exponentially fast, and we determine its precise exponent. Below the boundary, where the risk tends to $1$, we obtain matching absolute-constant bounds for its polynomial rate of convergence. In both regimes, the asymptotics change across the line α+δ=1/2, where δ parametrizes the signed distance from the detection boundary. Finally, on the boundary, we show that the minimax risk converges to the nondegenerate constant 1/2 in a very sparse regime where n remains fixed and N→∞. Each of these rates corresponds to the risk of a suitably calibrated scan or sum test, whence follow the upper bounds. The main problem is to derive the matching regime-specific lower bounds. The mixture likelihood ratio is an average rather than a product and thus its logarithm lacks the additive structure required by standard large deviation formulations. On the other hand, classical second-moment estimates fail to be sharp due to overlap-induced correlations. To address these issues, we develop two general lower-bound principles based on truncated mixture likelihoods, tailored to the target risks on both sides of the detection boundary. The same framework yields sharp risk asymptotics for sparse subtensors with equal side lengths and also applies to more general testing problems including the detection of rectangular subtensors.
ER -