The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910047728041984 |
|---|---|
| author | Erba, Vittorio Kupferschmid, Nathan Malo Ortiz, Rodrigo Pérez Zdeborová, Lenka |
| author_facet | Erba, Vittorio Kupferschmid, Nathan Malo Ortiz, Rodrigo Pérez Zdeborová, Lenka |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_15400 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties Erba, Vittorio Kupferschmid, Nathan Malo Ortiz, Rodrigo Pérez Zdeborová, Lenka Disordered Systems and Neural Networks Information Theory Probability 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. |
| title | The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties |
| topic | Disordered Systems and Neural Networks Information Theory Probability |
| url | https://arxiv.org/abs/2506.15400 |