Source-linked AI summary
RDT based upper bounds on the largest average submatrix values
Mihailo Stojnic
TL;DR
The paper addresses the lack of rigorous information-theoretic and algorithmic analysis for LASP in the linear regime. It develops plain and lifted RDT frameworks, obtaining explicit upper bounds and matching known asymptotic predictions, while LAS closely approaches the bounds over substantial ranges.
Problem
Rigorous results characterizing LASP and the possible statistical-computational gap in the linear regime remain limited.
Method
The paper develops a generic Random Duality Theory framework with plain and lifted variants for analyzing LASP.
Results
Lifted RDT strictly improves plain RDT in part of the linear range, matches replica and sublinear predictions as β →0, and LAS differs from theoretical bounds by no more than 0.1% across a significant range.
Takeaways & Limitations
The results provide rigorous linear-regime upper bounds and suggest that the SCG is absent or practically insignificant over at least part of the studied dimension range.
Takeaways & Limitations
Strong random duality is not established because the problem’s highly discrete structure prevents applying the relevant reversal considerations.
Abstract
from arXiv · showhide
We study statistical variants of the classical largest average submatrix problem. For small submatrices (where the dimension is less than linearly proportional to the original matrix), the problem is typically well understood and believed to exhibit the statistical-computational gap (SCG). However, analytical treatment of both the information-theoretic and algorithmic aspects of the linear regime remains challenging, and no mathematically rigorous results have yet arrived anywhere close to proving or disproving SCG existence in this setting. Focusing on the linear regime, we make strong progress in several key directions: 1) We develop a generic Random Duality Theory (RDT) framework to characterize largest average submatrix values. 2) Using the plain RDT variant, we obtain closed-form upper bounds as explicit functions of dimensionality proportionality parameters. 3) We demonstrate that a lifted RDT variant strictly improves upon the plain RDT within a certain linear range of submatrix dimensions. 4) For small submatrices where the dimensional proportionality constants approach zero, we prove that our results match both the replica results from [34] (obtained via one-step replica symmetry breaking) and the sublinear results from [18,45].
1 Introduction
The paper studies the largest average submatrix problem in a statistical proportional regime, where matrix and submatrix dimensions grow together. It uses Random Duality Theory to derive upper bounds for this problem.
- The statistical formulation treats problem instances as probabilistically generated, supporting analysis of typical algorithmic behavior beyond worst-case complexity.
- The largest average submatrix problem seeks the k1 × k2 submatrix with the greatest average entry value in a given matrix.
- The analysis assumes m, n, k1, and k2 are all large and proportional, placing the problem in the linear regime.
- Random Duality Theory provides a generic framework for analyzing these problems and ultimately determining upper bounds on ξ.
2 Technical preliminaries, prior work, and contributions
The paper formalizes LASP in a Gaussian statistical setting, reviews prior results across sublinear and linear regimes, and presents RDT-based contributions for general matrix dimensions. Its contributions include explicit bounds, lifted improvements, asymptotic matching, and comparisons with LAS performance.
- Prior work: Prior work established precise sublinear estimates, studied replica phase diagrams in the linear regime, and analyzed related tensor and planted variants.
- Contributions: The framework covers square and non-square matrices and submatrices, extending beyond the square settings common in prior work.
- Contributions: Plain RDT yields explicit, closed-form upper bounds whose dependence on dimensionality parameters is directly computable.
- Contributions: The lifted RDT variant strictly improves plain RDT over part of β ∈(0, 1), with the improvement characterized as β →0.
- Contributions: For β →0, the results match one-step symmetry-breaking replica predictions and extrapolate to sublinear results from.
- Contributions: For dimensions around 1000, LAS values closely approach the theoretical predictions, with differences of approximately 0.01% in certain β regimes.
3 Upper-bounding ξ via RDT
The paper applies RDT by constructing a random primal, deriving a random dual through Gaussian comparison arguments, and reducing the resulting expressions to bounds on Eξ. The resulting random dual provides an upper bound, while the discrete nature of LASP prevents strong random duality from making these bounds exact.
- RDT framework: RDT proceeds through an optimization representation, random-dual construction, and a final check of strong random duality.
- Random dual: The random primal is complemented by a random dual whose right-hand side upper-bounds the expected objective Eξ.
- Random dual: The random-dual derivation uses independent Gaussian vectors and Gaussian-process comparison results, including the Slepian lemma.
- Scope: The paper states results through expectations while noting that key quantities concentrate and that the conclusions extend probabilistically and apply to fixed dimensions.
- Upper bounds: Theorem 3 summarizes the resulting bound in the general proportional setting, with a squared-matrix specialization given in Corollary 1.
- Upper bounds: The small-submatrix specialization considers β →0 in the squared setting and yields the corresponding asymptotic bound.
- Strong random duality: Because LASP is highly discrete, the reversal arguments needed to establish strong random duality do not apply, leaving the derived upper bounds strictly bounded rather than exact.
4 Lowering upper bounds via lifted RDT
The lifted RDT methodology produces tighter upper bounds than plain RDT for largest average submatrix values, with improvements concentrated at small proportional submatrix sizes. In the small-submatrix limit, the bounds match replica and sublinear-regime results.
- 4.1 Handling lifted random dual: The lifting effect lowers the plain RDT bound by precisely a factor of 2 as β → 0.
- 4.1 Handling lifted random dual: For small submatrices, the lifted-RDT results match replica predictions obtained with one-step replica symmetry breaking.
- 4.1 Handling lifted random dual: The corresponding extrapolation to sublinear submatrices matches the results previously obtained in.
- 4.1 Handling lifted random dual: Lifted RDT improves upon plain RDT, with the lifting effect beginning near β ≈ 0.24 and emphasized for β ∈ (0, 0.2).The paper states that lifted RDT confirms strong RDT is not in place.
- 4.1 Handling lifted random dual: The framework yields concrete upper bounds as functions of β, illustrated in Figure 1, while LAS simulations closely approach the theoretical predictions.The supplied table caption identifies a higher-β theory-versus-simulation comparison; for β ≥ 0.7, LAS values are within 0.99 of RDT estimates.
5 Conclusion
The paper develops rigorous RDT-based bounds for LASP in the linear regime, where SCG evidence has been lacking, and compares them with LAS performance. Lifted RDT improves plain RDT in a range, while theory and a simple algorithm closely agree across substantial parameter regimes.
- Scope: The work targets LASP's linear regime, which previously lacked mathematically rigorous evidence establishing whether a statistical-computational gap exists.The study therefore addresses both theoretical bounds and algorithmic behavior in a regime distinct from the more thoroughly studied sublinear setting.
- RDT framework: The framework supplies closed-form plain and lifted RDT upper bounds, with lifted RDT strictly improving plain RDT over a range of linear submatrix dimensions.For small linear-regime submatrices, the results match replica predictions and extrapolated sublinear results.
- Theory versus algorithm: For a significant dimension range, LAS differs from the theoretical bounds by no more than 0.1%, even for matrices of roughly one thousand in size.Figure 2 compares theoretical RDT and lifted-RDT values with algorithmic LAS performance.