Pith. sign in

REVIEW 3 major objections 5 minor 18 references

Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For Gaussian data, every online algorithm for the densest submatrix problem is limited to 4/(3√2) of the optimum.

desk verdict The positive side is solid, but the negative half's key disjointness assertion is unproven and false for a trivial algorithm, so Theorem 2.3 is not established as written. read the letter →

arxiv 2507.19259 v1 pith:QHCEQ2IH submitted 2025-07-25 math.PR math.STstat.TH

Shankar Bhamidi , David Gamarnik , Shuyang Gong This is my paper · ORCID
classification math.PRmath.STstat.TH MSC 62G3260G7068Q17
keywords largeaveragesubmatrixonlinealgorithmsoverlapgappropertybranchingrandomtensorGaussianmatrixapproximationfactorcomputation-to-optimization
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies the densest fixed-size submatrix (and subtensor) problem for matrices and tensors with independent standard Gaussian entries, where density is the average entry value. It establishes that for online algorithms—sequential procedures that build their output one coordinate at a time, a class that includes the best known polynomial-time greedy procedure—no algorithm can beat a fixed fraction of the true optimum. For matrices that fraction is $4/(3\sqrt{2})\approx 0.9428$; for $p$-th order tensors it is $2\sqrt{p}/(1+p)$. A matching positive result shows that the existing Incremental Greedy Procedure already achieves this fraction with high probability, so the online class has a sharp approximation factor. If the paper is right, the long-suspected computation-to-optimization gap for this problem is fully explained within the online class, and any further improvement would require a non-online algorithm.

What carries the argument

The load-bearing object is the branching overlap gap property, implemented as a 'forbidden structure' (Definition 4.1): a $D$-regular tree of depth $N$ whose vertices carry disjoint coordinate sets $A_v^{(s)}\subset[n]$ at each depth, with each leaf $v$ indexing a sub-tensor $M_v$ built from the union of the sets along its root-to-leaf ray. The structure is forbidden when every leaf has average at least $(\kappa_p+\epsilon)\sqrt{2\log n/k^{p-1}}$ with $\kappa_p=2p/(p+1)$. Proposition 4.2 shows such structures have probability at most $\exp(-cpk\log n)$, by bounding a level-averaged Gaussian sum and choosing $D$ large enough to dominate the combinatorial enumeration of the coordinate sets. Lemma 4.4 converts any online algorithm into a candidate forbidden structure: on a $(T,\vec\alpha)$-correlated instance, where each vertex carries an independent Gaussian tensor and each leaf sees blocks from its ancestor tensors, conditional independence plus Jensen's inequality upgrades a single-instance success probability $p_{\mathrm{suc}}$ to success on all leaves with probability at least $p_{\mathrm{suc}}^{|L|}$. Comparing the two bounds forces $p_{\mathrm{suc}}\le \exp(-(c/D^N)k\log n)$.

What would settle it

Run an online algorithm on a $(T,\vec\alpha)$-correlated instance with two sibling leaves and inspect the coordinate sets chosen at the same depth in $A(G_v)$ and $A(G_{v'})$; a single shared row or column index at a common depth violates the disjointness required by Definition 4.1. Producing such an instance-family would show the proof of Theorem 2.3 does not cover all algorithms in OLA as defined.

Watch

Extended reading notes

Core claim

The paper proves Theorem 2.3: for a tensor $G\in(\mathbb R^n)^{\otimes p}$ with i.i.d. standard normal entries, $k=k_n\to\infty$, and every $\epsilon>0$, there is $c=c(\epsilon,p)>0$ such that every online algorithm $A$ satisfies $$P\left[\mathrm{Ave}(A(G))\ge \left(\frac{2p}{p+1}+\epsilon+o_k(1)\right)\sqrt{\frac{2\log n}{$k^{{p-1}}$}}\right]\le \exp(-ck\log n).$$ Since the Incremental Greedy Procedure is online and, by Theorem 2.1, attains the matching value $\left(\frac{2p}{p+1}-o_k(1)\right)\sqrt{2\log n/k^{p-1}}$ with probability $1-o(1)$, the online class has approximation factor exactly $2\sqrt{p}/(1+p)$ relative to the tensor optimum $\sqrt{2p\log n/k^{p-1}}$. For $p=2$, this factor is $4/(3\sqrt{2})\approx 0.9428$, recovering the value $\frac{4}{3}\sqrt{2\log n/k}$ that the Incremental Greedy Procedure was already known to reach.

Load-bearing premise

The argument treats the outputs $A(G_v)$ on the correlated leaf instances as a forbidden structure whose coordinate sets at each tree depth are disjoint; if two branches of the tree choose overlapping indices, the Gaussian tail bound that rules out the forbidden structure no longer applies.

Editorial extensions

If this is right

  • The Incremental Greedy Procedure is optimal within the online class: no online algorithm can whp produce an average larger than $(\frac{2p}{p+1}+o_k(1))\sqrt{2\log n/k^{p-1}}$.
  • For tensor order $p$, the relative gap $1-\frac{2\sqrt p}{1+p}$ grows with $p$, so higher-order tensors admit a larger gap between the online barrier and the true optimum.
  • Any polynomial-time algorithm that beats this factor must lie outside the online class as defined in Definition 2.2; the paper does not rule out such algorithms.
  • The branching-OGP proof supplies an elementary template for other dense-substructure problems where an ultrametric tree of high-value solutions can be ruled out by a Gaussian tail estimate.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: the upper-bound argument uses only Gaussian tail bounds and block independence, so the same constant should hold for sub-Gaussian entries with matching sub-Gaussian norm; the paper does not claim this extension.
  • Editorial extension: the online barrier suggests that two-pass or backtracking algorithms are the natural candidates to close the remaining gap, since they are not constrained by the sequential coordinate-by-coordinate rule that the proof exploits.
  • Editorial extension: a finite-size simulation of the Incremental Greedy Procedure on standard normal matrices could test whether empirical averages track $4/(3\sqrt{2})$ of the predicted optimum with finite-size corrections of order $1/\sqrt{k}$; the paper reports no simulations.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies the problem of finding a k×⋯×k subtensor of maximum average value in an n^{⊗p} tensor with i.i.d. standard Gaussian entries. It proves a positive result, Theorem 2.1, showing that a generalized incremental greedy procedure (IGP) achieves average value asymptotic to (2p/(p+1))√(2 log n / k^{p−1}) with high probability when k=exp(o(log n)). It then claims a matching upper bound, Theorem 2.3, for the class of online algorithms (OLA), defined by a causal blockwise information constraint in Definition 2.2. The upper bound is established via a branching overlap gap property (OGP): a tree-indexed family of subtensors with large sums is shown to be exponentially unlikely (Proposition 4.2), and success of an OLA on a correlated tree instance is asserted to produce such a forbidden family. The final step, appearing just before Eq. (27), is the crucial reduction from OLA outputs to the forbidden structure of Definition 4.1.

Significance. If valid, Theorem 2.3 would give a sharp constant-factor characterization of the approximability of dense submatrix/subtensor search within a natural algorithmic class, and would showcase the branching-OGP method in a new setting. The positive side is a clean, self-contained Gaussian-tail argument, and the abstract forbidden-structure probability bound in Proposition 4.2 is coherent for the abstract tree family considered there. The weakness is the reduction from OLA to forbidden structures in Section 4.2, which is the load-bearing step for Theorem 2.3 and is, as written, not justified. The claimed optimality of IGP within OLA is therefore not established by this manuscript.

major comments (3)
  1. [Section 4.2, sentence before Eq. (27)] The assertion that if Suc_A(G^v) holds for all leaves v then {A(G^v)}_{v∈L} forms a forbidden structure according to Definition 4.1 is not a consequence of the online definition. Definition 4.1 requires, for each mode s, the sets A_v^{(s)} to be pairwise disjoint over distinct vertices v, v'. Definition 2.2 constrains each single run causally: the layer chosen at step s may depend only on entries indexed by coordinates at most ⌊s/k n⌋ and on the previous layers of the same run. It imposes no relation between the indices chosen in different runs on different leaves of a (T,α)-correlated instance. For example, the constant algorithm that always outputs the subtensor indexed by {1,…,k} in every mode belongs to OLA. On the event that this fixed subtensor has sum at least (2p/(p+1)+ε)D_n for every leaf G^v, Suc_A(G^v) holds for all v, but the fixed output supplies only k coordinate indices per mode, whereas the forbidden structure would require disjoint sets A_v^{(s)} whose total size across the tree is k∑_{ℓ=1}^N D^{ℓ−1}(α_ℓ−α_{ℓ−1}) > k for D>1. Thus the disjointness condition cannot be met, and Proposition 4.2 cannot be invoked. Consequently the bound p_suc^{|L|} ≤ exp(−ck log n) in Eq. (27) does not follow.
  2. [Section 4.2 / Definition 2.2] The proof does not specify how the k sequential layers of an OLA algorithm are mapped to the N layers of the tree in Definition 4.1. Definition 2.2 has a layer for each step r=1,…,k, with information thresholds ⌊r/k n⌋, while Definition 4.1 uses an arbitrary partition 0=α_0<α_1<⋯<α_N=1 and requires sets A_v^{(s)} of sizes (α_j−α_{j−1})k for each tree vertex at depth j. The text never defines the sets A_v^{(s)} from the online algorithm's output, nor proves the size identity, nor explains how the thresholds align with the α_j, for instance through integers s_j≈α_j k. As written, the reduction from OLA to a forbidden structure is not a well-defined map, so the contradiction in Theorem 2.3 is not rigorously formulated.
  3. [Section 4.1, Eq. (21)–(22)] The Gaussian tail computation in Proposition 4.2 is valid only for the abstract forbidden structure where the entry sets E_v are disjoint across vertices at each depth. This is where the variance D^{ℓ−1}(α_ℓ^p−α_{ℓ−1}^p)k^p in Eq. (21) comes from, and it is used to justify the exponent in Eq. (22). Because the reduction in Theorem 2.3 cannot guarantee disjointness of the sets A_v^{(s)} for OLA outputs, the estimate exp(−ck log n) in Eq. (12) does not transfer to the event that all leaves of the correlated instance succeed. If the sets overlap, the same Gaussian entries contribute to multiple E_v, and the variance in Eq. (21) is no longer correct, so the tail bound in Eq. (22) has no justification in the context of Theorem 2.3.
minor comments (5)
  1. [Proof of Theorem 2.3, just before Eq. (27)] The text says 'forms forbidden structure according to Definition 2.2'; this should be Definition 4.1.
  2. [Eq. (17) and Eq. (22)] The index i is used both for the level ℓ and as a summation index; for example, 'α_i−1' should be 'α_{ℓ−1}' and 'α_i' should be 'α_ℓ' in the sums over j.
  3. [Theorem 2.3 statement] Writing o_k(1) inside the probability event is nonstandard, since the event depends on k in a way that is not monotone. It would be cleaner to state that for every ε>0 there is k_0 such that for all k≥k_0, P[Avg(A(G)) ≥ (2p/(p+1)+ε)√(2 log n / k^{p−1})] ≤ exp(−c k log n).
  4. [Lemma 3.1] The statement says 'for all 1≤r≤k, 1≤s≤p', but for r=1 some variances r^{s−1}(r−1)^{p−s} vanish when p>1 and s>1; the lemma should explicitly restrict to 2≤r≤k or define the quantities only for r≥2.
  5. [Eq. (5)] The partition of [n] into k+1 disjoint sets is only partially described: the first k sets P_{i,n} are defined, but the (k+1)-st set is not. Since only P_{1,n},…,P_{k,n} are used, this is harmless but should be clarified.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: constants are derived from Gaussian estimates and Riemann sums, not fitted; the main caveat is an omitted structural verification, not a circular reduction.

full rationale

The central derivation is self-contained. For the positive side, Theorem 2.1 is proved directly from Lemma 3.1 using Gaussian tail estimates and a Riemann-sum identity that yields the constant 2p/(p+1). For the hardness side, Theorem 2.3 relies on Definition 4.1 and Proposition 4.2, whose variance computation and union bound are carried out explicitly in the paper, and on Lemma 4.4, whose conditional-independence and Jensen argument is given in full. No fitted parameter is renamed as a prediction, and the constant 2p/(p+1) is not imported from the success definition or from a cited theorem; it is computed. The branching-OGP method is attributed to Huang-Sellke [14], and the construction is said to follow [5], which includes author Gong, but the present paper re-proves the needed bounds rather than importing the conclusion, so these self-citations are background and not load-bearing. The only substantive concern is an omitted verification, not circularity: immediately before (27) the proof asserts that if Suc_A(Gv) holds for all leaves, then '{A(Gv)}v∈L forms forbidden structure according to Definition 2.2' (apparently meaning Definition 4.1). Definition 4.1 requires the per-level coordinate sets A_v^(s) to be disjoint across distinct vertices, and this disjointness is not implied by the online condition in Definition 2.2 as written; the variance estimate in Proposition 4.2, especially (21)-(23), depends on that disjointness. This is a correctness gap in the claimed proof, but it is not a circular reduction of the theorem to its own assumptions.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The central claim introduces no fitted constants: the approximation factors come from evaluating the integral 2p/(p+1). The only hand-chosen quantities are proof parameters (partition, tree degree) that do not enter the final bound's leading constant. Axioms are the Gaussian model, the online class, and prior OGP machinery.

free parameters (2)
  • partition length N(ε,p) and mesh α_0,...,α_N = chosen satisfying (8)
    Hand-chosen asymptotic proof parameters; affect the rate exponent c in Theorem 2.3, not the limiting factor.
  • tree degree D = large constant satisfying (9)
    Hand-chosen in Proposition 4.2 to make the union bound negative.
assumptions (5)
  • domain assumption Entries of the matrix/tensor are i.i.d. N(0,1) Gaussian
    Central model; Gaussian tail bounds and independence are used throughout.
  • domain assumption k = exp(o(log n)) for the positive side
    Theorem 2.1 assumes k=exp(o(log n)); Theorem 2.3 only states k→∞ but the block partitions suggest a similar small-k regime.
  • domain assumption Online algorithm is sequential and its r-th increment is determined by the first r n/k entries
    Definition 2.2; the hardness result is for this specific class.
  • standard math Standard Gaussian tail and Riemann integral estimates
    Used in Lemmas 3.1 and Proposition 4.2.
  • domain assumption Branching-OGP framework from [14] and [5] is valid
    The paper builds on these results without re-deriving their core properties.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms." pith.science (2026). https://pith.science/paper/QHCEQ2IH

@misc{pith2026250719259,
  author       = {Pith},
  title        = {Pith review of: Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QHCEQ2IH}},
  note         = {Machine review of arXiv:2507.19259}
}
abstract

We consider the problem of finding a dense submatrix of a matrix with i.i.d. Gaussian entries, where density is measured by average value. This problem arose from practical applications in biology and social sciences \cites{madeira-survey,shabalin2009finding} and is known to exhibit a computation-to-optimization gap between the optimal value and best values achievable by existing polynomial time algorithms. In this paper we consider the class of online algorithms, which includes the best known algorithm for this problem, and derive a tight approximation factor ${4\over 3\sqrt{2}}$ for this class. The result is established using a simple implementation of recently developed Branching-Overlap-Gap-Property \cite{huang2025tight}. We further extend our results to $(\mathbb R^n)^{\otimes p}$ tensors with i.i.d. Gaussian entries, for which the approximation factor is proven to be ${2\sqrt{p}/(1+p)}$.

Figures

Figures reproduced from arXiv: 2507.19259 by the authors.

Figure 1
Figure 1. In the setting p = 2, showing density of points covered by Ev Summing over the above expression and then taking the average, we get X N ℓ=1 1 Dℓ−1 X v:|v|=ℓ γ ∗ v ≥ κp + ϵ . (16) Using (16) and (8), we have that there exists an ℓ ∈ [N] such that 1 Dℓ−1 X v:|v|=ℓ γ ∗ v ≥ κp + ϵ κp + ϵ/10 (αℓ − αℓ−1) vuutp X p−1 j=0 (αi−1) j (αi) p−1−j =(1 + δ)(αℓ − αℓ−1) vuutp X p−1 j=0 (αi−1) j (αi) p−1−j . (17) We denote the above … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 17 canonical work pages

  1. [14]

    Huang and M

    B. Huang and M. Sellke, Tight lipschitz hardness for optimizing mean field spin glasses , Communications on Pure and Applied Mathematics 78 (2025), no. 1, 60–119

    work page 2025

  2. [5]

    H. Du, S. Gong, and R. Huang, The algorithmic phase transition of random graph alignment problem , Probability Theory and Related Fields (2025), 1–56

    work page 2025

  3. [1]

    Bhamidi, P

    S. Bhamidi, P. S Dey, and A. B Nobel, Energy landscape for large average submatrix detection problems in gaussian random matrices, Probability Theory and Related Fields 168 (2017), 919–983

    work page 2017

  4. [2]

    Bodwin, K

    K. Bodwin, K. Zhang, and A. Nobel, A testing based approach to the discovery of differentially correlated variable sets, The annals of applied statistics 12 (2018), no. 2, 1180

    work page 2018

  5. [3]

    Cai and T

    T T. Cai and T. Jiang, Limiting laws of coherence of random matrices with applications to testing covariance structure and construction of compressed sensing matrices , The Annals of Statistics (2011), 1496–1525

    work page 2011

  6. [4]

    Dewaskar, J

    M. Dewaskar, J. Palowitch, M. He, M. I Love, and A. B Nobel, Finding groups of cross-correlated features in bi-view data, Journal of Machine Learning Research 24 (2023), no. 398, 1–47. 10

    work page 2023

  7. [6]

    V. Erba, N. M. Kupferschmid, R. P´ erez, and L. Zdeborov´ a,The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties, 2025. Work in progress

    work page 2025

  8. [7]

    Gamarnik, The overlap gap property: A topological barrier to optimizing over random structures , Proceedings of the National Academy of Sciences 118 (2021), no

    D. Gamarnik, The overlap gap property: A topological barrier to optimizing over random structures , Proceedings of the National Academy of Sciences 118 (2021), no. 41, e2108492118

    work page 2021

Show all 18 references
  1. [8]

    Gamarnik, Turing in the shadows of nobel and abel: an algorithmic story behind two recent prizes , Notices of AMS 72 (2025), no

    D. Gamarnik, Turing in the shadows of nobel and abel: an algorithmic story behind two recent prizes , Notices of AMS 72 (2025), no. 5

    2025

  2. [9]

    Gamarnik, E

    D. Gamarnik, E. C Kizilda˘ g, W. Perkins, and C. Xu, Geometric barriers for stable and online algorithms for discrepancy minimization, The thirty sixth annual conference on learning theory, 2023, pp. 3231–3263

    2023

  3. [10]

    Gamarnik, E

    D. Gamarnik, E. C Kızılda˘ g, and L. Warnke, Optimal hardness of online algorithms for large independent sets , arXiv preprint arXiv:2504.11450 (2025)

    2025

  4. [11]

    Gamarnik and Q

    D. Gamarnik and Q. Li, Finding a large submatrix of a gaussian random matrix , The Annals of Statistics 46(6A) (2018), 2511–2561

    2018

  5. [12]

    Gamarnik, C

    D. Gamarnik, C. Moore, and L. Zdeborov´ a, Disordered systems insights on computational hardness , Journal of Statistical Mechanics: Theory and Experiment 2022 (2022), no. 11, 114015

    2022

  6. [13]

    A. K. R. Hegade and E. C Kızılda˘ g,Large average subtensor problem: Ground-state, algorithms, and algorithmic barriers, arXiv preprint arXiv: 2506.17118 (2025)

    2025 arXiv

  7. [15]

    S. C. Madeira and A. L. Oliveira, Biclustering algorithms for biological data analysis: a survey , Computational Biology and Bioinformatics, IEEE/ACM Transactions on 1 (march 2004jan.), no. 1, 24 –45

  8. [16]

    Mosso, K

    C. Mosso, K. Bodwin, S. Chakraborty, K. Zhang, and A. B Nobel, Latent association mining in binary data , arXiv preprint arXiv:1711.10427 (2017)

    2017 arXiv

  9. [17]

    Pontes, R

    B. Pontes, R. Gir´ aldez, and J. S Aguilar-Ruiz, Biclustering on expression data: A review , Journal of biomedical informatics 57 (2015), 163–180

    2015

  10. [18]

    A. A. Shabalin, V. J. Weigman, C. M. Perou, and A. B. Nobel, Finding large average submatrices in high dimensional data, The Annals of Applied Statistics 3 (2009), no. 3, 985–1012. 11

    2009

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.