Abstract
In this paper we introduce and study the Maximum-Average Subtensor ($p$-MAS) problem, in which one wants to find a subtensor of size $k$ of a given random tensor of size $N$, both of order $p$, with maximum sum of entries. We are motivated by recent work on the matrix case of the problem in which several equilibrium and non-equilibrium properties have been characterized analytically in the asymptotic regime $1 \ll k \ll N$, and a puzzling phenomenon was observed involving the coexistence of a clustered equilibrium phase and an efficient algorithm which produces submatrices in this phase. Here we extend previous results on equilibrium and algorithmic properties for the matrix case to the tensor case. We show that the tensor case has a similar equilibrium phase diagram as the matrix case, and an overall similar phenomenology for the considered algorithms. Additionally, we consider out-of-equilibrium landscape properties using Overlap Gap Properties and Franz-Parisi analysis, and discuss the implications or lack thereof for average-case algorithmic hardness.
Introduction
The Maximum-Average Subtensor ($p$-MAS) problem explores a fascinating intersection between statistical physics and computer science. It investigates why certain optimization problems remain computationally "easy" for algorithms even when their mathematical landscapes suggest they should be "hard." Specifically, the problem asks: given a massive, $p$-dimensional cube of random numbers (a tensor), can we find a smaller subtensor of size $k$ with the highest possible average value?
In the study of random landscapes, this often leads to a "computational-to-statistical gap." As one searches for increasingly optimal solutions, the landscape typically undergoes a phase transition where the solution space "shatters" from a single connected component into a vast number of tiny, isolated islands (clusters). Standard intuition suggests that once this "freezing" occurs, efficient algorithms should fail. However, previous work on the matrix version ($p=2$) showed that simple greedy algorithms could navigate this shattered landscape. This paper extends that analysis to higher-order tensors ($p > 2$).
Theoretical Framework and Methods
The authors treat the $p$-MAS problem as a statistical mechanics system by mapping it onto a Boolean $p$-spin glass model. They utilize several advanced theoretical frameworks to probe the landscape:
- Replica Theory (1-RSB): To map the equilibrium phase diagram and identify where the solution space shatters into a "frozen" phase.
- Greedy Algorithms: Analysis of the Largest Average Submatrix (LAS) and the Incremental Greedy Procedure (IGP). The IGP works by starting with a single entry and greedily adding the "best" remaining slices one by one.
- Overlap Gap Property (OGP): A mathematical tool used to identify algorithmic hardness by showing that no two "good" solutions are at a medium distance from each other.
- Franz-Parisi Analysis: A technique to probe the local environment around a typical solution to determine if it is truly isolated or surrounded by a "cloud" of other viable solutions.
Landscape Analysis and Algorithmic Performance
The most significant insight is that the IGP algorithm successfully finds solutions deep within the "frozen 1-RSB" phase. In many other problems, such as the Binary Perceptron, this phase is a barrier for efficient algorithms. Here, the transition from matrices ($p=2$) to tensors ($p>2$) does not change this fundamental phenomenology; the thresholds shift, but the overall behavior remains consistent.
As summarized in the table above, the analytical results show a clear hierarchy: $a_{freezing} < a_{IGP} < a_{OGP} < a_{max}$. This confirms the existence of a wide regime where the landscape is theoretically shattered, yet an efficient algorithm (IGP) continues to function effectively. The "annealed" Overlap Gap Property provides an upper bound on hardness, but it still fails to explain why the IGP algorithm is so resilient to the shattered landscape.
Discussion and Future Directions
While the paper provides a rich picture of the $p$-MAS landscape—including the discovery of "planted clusters" through Franz-Parisi analysis—the fundamental reason for the algorithm's success remains elusive. The study highlights a puzzling gap in our understanding of what truly makes a random optimization problem computationally hard.
Future work may involve more rigorous "quenched" OGP analyses or testing these results against other hardness frameworks, such as "Low-Degree Polynomials" or "Sum-of-Squares," to see if they offer a more complete explanation for the IGP algorithm's effectiveness in seemingly hostile landscapes.
Summary updated