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

CardsList
  1. Low-Degree Method Fails to Predict Robust Subspace Recovery

    Mar 3, 2026He Jia, Aravindan VijayaraghavanLow-Degree Polynomial Method

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

    Jun 3, 2026Anda Skeja, Daniel Gutiérrez Espinoza, Fiona Skerman +1Two-Sample TestingLow-Degree Polynomial Method