stat.MLSep 11, 2025

Low-degree lower bounds via almost orthonormal bases

Authors: Alexandra Carpentier, Simone Maria Giancola, Christophe Giraud, Nicolas Verzelen

Organizations: LMO, CELESTE · MISTEA

Abstract

Low-degree polynomials have emerged as a powerful paradigm for providing evidence of statistical--computational gaps across a variety of high-dimensional statistical models [Wein25]. For detection problems---where the goal is to test a planted distribution P′\mathbb{P}' against a null distribution P\mathbb{P} with independent components---the standard approach is to bound the advantage using an L2(P)\mathbb{L}^2(\mathbb{P})-orthonormal family of polynomials. However, this method breaks down for estimation tasks or more complex testing problems where P\mathbb{P} has some planted structures, so that no simple L2(P)\mathbb{L}^2(\mathbb{P})-orthogonal polynomial family is available. To address this challenge, several technical workarounds have been proposed [SW22,SW25], though their implementation can be delicate. In this work, we propose a more direct proof strategy. Focusing on random graph models, we construct a basis of polynomials that is almost orthonormal under P\mathbb{P}, in precisely those regimes where statistical--computational gaps arise. This almost orthonormal basis not only yields a direct route to establishing low-degree lower bounds, but also allows us to explicitly identify the polynomials that optimize the low-degree criterion. This, in turn, provides insights into the design of optimal polynomial-time algorithms. We illustrate the effectiveness of our approach by recovering known low-degree lower bounds, and establishing new ones for problems such as hidden subcliques, stochastic block models, and seriation models.

Explore similar work

Mar 3, 2026

Low-Degree Method Fails to Predict Robust Subspace Recovery

The low-degree polynomial framework has been highly successful in predicting computational versus statistical gaps for high-dimensional problems in average-case analysis and machine learning. This success has led to the low-degree conjecture, which posits that this method captures the power and limitations of efficient algorithms for a wide class of high-dimensional statistical problems. We identify a natural and basic hypothesis testing problem in Rn\mathbb{R}^n which is polynomial time solvable, but for which the low-degree polynomial method fails to predict its computational tractability even up to degree k=nΩ(1)k=n^{Ω(1)}. Moreover, the low-degree moments match exactly up to degree k=O(log⁡n/log⁡log⁡n)k=O(\sqrt{\log n/\log\log n}). Our problem is a special case of the well-studied robust subspace recovery problem. The lower bounds suggest that there is no polynomial time algorithm for this problem. In contrast, we give a simple and robust polynomial time algorithm that solves the problem (and noisy variants of it), leveraging anti-concentration properties of the distribution. Our results suggest that the low-degree method and low-degree moments fail to capture algorithms based on anti-concentration, challenging their universality as a predictor of computational barriers.
Jun 3, 2026

Sharp Low-Degree Thresholds for Planted-vs-Planted Testing

We establish the first sharp thresholds for low-degree polynomial tests in planted-vs-planted settings, where the goal is to determine with vanishing error which of two structured planted mechanisms generated the observed data. We prove matching low-degree upper and lower bounds for counting communities in the planted submatrix and planted dense subgraph models. The resulting testing threshold coincides, down to the sharp constant, with the known low-degree recovery threshold. In contrast, the task of weak testing, where the goal is to outperform random guessing, does not have a sharp threshold but rather a smooth transition, which we identify. To prove our results, we develop a framework for planted-vs-planted testing that builds on a latent-variable expansion originating in low-degree recovery and employs new methods to identify and prune non-signal contributions.
Oct 27, 2026

Low-degree polynomials lower bounds for clustering in small dimension

We study the computational limits of clustering nn observations drawn from a mixture of KK isotropic distributions in Rd\mathbb R^d, in the regime where the number KK of groups is much larger than the dimension dd. In this regime, tensor-based procedures recover the partition with a polylogarithmic separation between the centers, but they require a sample size that is a large and non-explicit polynomial of dKdK, whereas the existing low-degree lower bounds only show that nn must be larger than dK2dK^2. We introduce a mixture of 2K2K product Bernoulli distributions on {0,1}d\{0,1\}^d, with K=(d+1)mK=(d+1)^m, whose centers are built from a dual BCH code. This construction ensures that the moment tensors of the observations coincide with those of the uniform distribution on {−1,1}d\{-1,1\}^d up to the order 2m+12m+1. For any fixed mm, we establish a low-degree polynomial lower bound showing that clustering is hard as long as the separation ΔΔ satisfies Δ2≪(K2d3/2/n)1/(2m+2)∧dΔ^2\ll(K^2d^{3/2}/n)^{1/(2m+2)}\wedge\sqrt d, up to polylogarithmic factors. In particular, with a polylogarithmic separation, low-degree polynomials require n≳K2d3/2n\gtrsim K^2d^{3/2} observations, up to polylogarithmic factors. Through a Gaussianization argument, this hardness carries over, in the sense of reductions, to isotropic Gaussian mixtures. Our proof relies on a family of polynomials of the observations, indexed by bipartite graphs, which is almost orthonormal. The moments of these polynomials are governed by the number of solutions of polynomial systems over the finite field F_d+1\mathbb F\_{d+1} that are induced by the BCH code, and the crux of our analysis is to connect the combinatorial structure of the bipartite graphs with the structure of the solution sets of these systems.