The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties

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.

References in corpus (29)

• The structural glass transition and the entropy of the metastable states
• Statistical physics of inference: Thresholds and algorithms
• Recipes for metastable states in Spin Glasses
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Shaping the learning landscape in neural networks around wide flat minima
• Origin of the computational hardness for learning with binary synapses
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Storage capacity in symmetric binary perceptrons
• Disordered Systems Insights on Computational Hardness
• Entropy landscape of solutions in the binary perceptron problem
• Clustering of solutions in the symmetric binary perceptron
• The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
• Estimating rank-one matrices with mismatched prior and noise: universality and large deviations
• On the Atypical Solutions of the Symmetric Binary Perceptron
• On the free energy of vector spin glasses with non-convex interactions
• High-dimensional manifold of solutions in neural networks: insights from statistical physics
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Statistical mechanics of the maximum-average submatrix problem
• Local equations describe unreasonably efficient stochastic algorithms in random K-SAT
• Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
• Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
• Boolean SK Model
• Finding the right path: statistical mechanics of connected solutions in constraint satisfaction problems
• Optimal Hardness of Online Algorithms for Large Independent Sets
• Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms
• Algorithmic thresholds in combinatorial optimization depend on the time scaling