Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers

Abstract

We introduce the large average subtensor problem: given an order-p tensor over ℝ^N×⋯× N with i.i.d. standard normal entries and a k∈ℕ, algorithmically find a k×⋯× k subtensor with a large average entry. This generalizes the large average submatrix problem, a key model closely related to biclustering and high-dimensional data analysis, to tensors. For the submatrix case, <cit.> explicitly highlight the regime k=Θ(N) as an intriguing open question. Addressing the regime k=Θ(N) for tensors, we establish that the largest average entry concentrates around an explicit value E_max, provided that the tensor order p is sufficiently large. Furthermore, we prove that for any γ>0 and large p, this model exhibits multi Overlap Gap Property (m-OGP) above the threshold γ E_max. The m-OGP is a rigorous barrier for a broad class of algorithms exhibiting input stability. These results hold for both k=Θ(N) and k=o(N). For smaller values of k, we also propose a polynomial-time algorithm that finds a subtensor with an average entry of order Θ_p(1/√(p))E_max. In particular, the m-OGP is asymptotically sharp: onset of the m-OGP and the algorithmic threshold match as p grows. Our results show that while the case k=Θ(N) remains open for submatrices, it can be rigorously analyzed for tensors in the large p regime. This is achieved by interpreting the model as a Boolean spin glass and drawing on insights from recent advances in the Ising p-spin glasses.