Report on 2506.15400v3

Vittorio Erba, Nathan Malo Kupferschmid, Rodrigo Pérez Ortiz, Lenka ZdeborováOpenalex Unknown 2025 · DOI · arXiv · OpenAlex

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:

  1. Incremental Greedy Procedure (IGP): An algorithm that builds the subtensor step-by-step.
  2. 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.

Table 1: Analytical thresholds for the p-MAS problem across different models and properties.

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

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 [1-3] in which several equilibrium and non-equilibrium properties have been characterized analytically in the asymptotic regime 1 k 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.Concurrent work: algorithmic properties for large p.Shortly after our manuscript became publicly available, another relevant work was posted [38].In that work, the authors study the p-MAS problem for both k N and k N in the large p limit.They characterize the maximum subtensor average achievable, and they prove algorithmic hardness through an m-body OGP computation, drawing and extending results for the Ising p-spin model.The results of [38] are compatible with the Random Energy Model [39] intuition we provide in Section 3.4, and with our result for simple OGP (Section 5).Organization of the manuscript.The manuscript is organized as follows.In Section 2 we define the p-MAS problem and highlights the mapping onto a Boolean p-spin model.In Section 3 we present the replica equilibrium analysis for the p-MAS problem, and discuss the phase diagram for k N .In Section 4 we considers previously studied greedy algorithms for the matrix case, and analyze their performance in the tensor problem.In Section 5 we discuss overlap gap properties, and derive the annealed multi-body OGP thresholds for the p-MAS problem.In Section 6 we present the Franz-Parisi analysis of the matrix p = 2-MAS problem, and discuss the apparent lack of algorithmic insights given by this framework.
BibTeX
@inproceedings{erba2025report,
  author = {Vittorio Erba and Nathan Malo Kupferschmid and Rodrigo Pérez Ortiz and Lenka Zdeborová},
  title = {{Report on 2506.15400v3}},
  booktitle = {Openalex Unknown},
  year = {2025},
  doi = {10.21468/scipost.report.12461},
}

Loading related content...

Figure