Report on 2506.15400v3: The Maximum-Average Subtensor Problem
Abstract
This report explores the Maximum-Average Subtensor ($p$-MAS) problem, generalizing previous work on the matrix case ($p=2$) to higher-order tensors. We investigate the equilibrium and non-equilibrium properties of finding a $k$-sized subtensor with the maximum sum of entries within a random $N$-sized tensor of order $p$. Despite the emergence of a "shattered" landscape where solutions form isolated clusters (a frozen 1-RSB phase), simple greedy algorithms like the Incremental Greedy Procedure (IGP) demonstrate surprising efficiency. Our analysis reveals that the "computational-to-statistical gap" observed in matrices persists in tensors, challenging standard landscape-based hardness predictions.
Introduction
The task of identifying high-value structures within noisy data is a fundamental challenge in data science and statistical physics. The Maximum-Average Subtensor ($p$-MAS) problem serves as a benchmark for understanding how algorithmic performance relates to the geometric landscape of the solution space. Building on the "puzzling phenomenon" observed in the matrix case—where greedy algorithms succeed despite a clustered equilibrium phase—this study extends these findings to the tensor regime ($p > 2$).
Problem Definition and Mapping
The $p$-MAS problem involves finding a subtensor of size $k$ within a larger random tensor of size $N$ (both of order $p$) that maximizes the average value of its entries. By mapping this problem onto a Boolean $p$-spin model, the authors utilize tools from the physics of disordered systems to characterize its properties. The entries of the tensor are assumed to be independent, identically distributed (i.i.d.) standard Gaussian variables.
Equilibrium and Landscape Analysis
Using the one-step Replica Symmetry Breaking (1-RSB) ansatz, the researchers identified a phase diagram qualitatively identical to the matrix case. As the target average value increases, the solution space undergoes a transition from a connected Replica Symmetric (RS) phase to a "frozen" 1-RSB phase. In this frozen regime, solutions are isolated points, which typically suggests computational hardness for local search algorithms.
To further probe this landscape, the authors applied the Overlap Gap Property (OGP) and Franz-Parisi analysis. These tools are designed to detect "gaps" in the solution space that might hinder algorithms. However, the study finds that standard landscape probes fail to fully explain the success of certain greedy strategies.
Algorithmic Performance
The study focuses on two primary algorithms:
- Incremental Greedy Procedure (IGP): An algorithm that builds the subtensor step-by-step.
- Largest Average Submatrix (LAS): A local search variant that refines a candidate subtensor.
A key finding is that the IGP consistently outperforms the LAS algorithm. While LAS gets "stuck" at the freezing threshold, IGP reaches subtensor averages well into the frozen region, effectively navigating the shattered landscape.
Key Results
The analytical thresholds for various properties are summarized in the table below. Notably, the IGP performance threshold ($a_{IGP}$) is higher than the freezing threshold ($a_{freezing}$), confirming that the algorithm succeeds where equilibrium-based sampling would fail.
As the tensor order $p$ increases, the problem's behavior approaches that of the Random Energy Model (REM), where correlations vanish and the problem becomes intrinsically harder.
Conclusion
The generalization of the $p$-MAS problem to tensors confirms that the "greedy advantage" is a robust feature across different orders of $p$. The failure of standard landscape probes like the Franz-Parisi potential to predict IGP success suggests that these algorithms explore regions of the configuration space that are "invisible" to equilibrium-based tools. Future work may involve more sophisticated "branching" OGP analyses or testing the problem against other hardness frameworks like Sum-of-Squares (SoS) to bridge the remaining gap between theory and algorithmic performance.
Summary updated