Statistical mechanics of the maximum-average submatrix problem

Abstract

We study the maximum-average submatrix problem, in which given an $N\times N$ matrix $J$ one needs to find the $k\times k$ submatrix with the largest average of entries. We study the problem for random matrices $J$ whose entries are i.i.d. random variables by mapping it to a variant of the Sherrington-Kirkpatrick spin-glass model at fixed magnetization. We characterize analytically the phase diagram of the model as a function of the submatrix average and the size of the submatrix $k$ in the limit $N\to \infty$. We consider submatrices of size $k=mN$ with $0<m<1$. We find a rich phase diagram, including dynamical, static one-step replica symmetry breaking and full-step replica symmetry breaking. In the limit of $m\to 0$, we find a simpler phase diagram featuring a frozen 1-RSB phase, where the Gibbs measure is composed of exponentially many pure states each with zero entropy. We discover an interesting phenomenon, reminiscent of the phenomenology of the binary perceptron: there exist efficient algorithms that provably work in the frozen 1-RSB phase.

References in corpus (10)

• The structural glass transition and the entropy of the metastable states
• Phase Transitions in the Coloring of Random Graphs
• Finding large average submatrices in high dimensional data
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems
• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Locked constraint satisfaction problems
• Disordered Systems Insights on Computational Hardness
• A frozen glass phase in the multi-index matching problem

Cited by in corpus (3)

• Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties