Low-Degree Polynomial Method

Latest papers

15 papers2 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Oct 11, 2026

Adaptive Robust Confidence Sets in High Dimensions

We study adaptive confidence sets for mean vectors of multivariate Gaussians with identity covariance under Huber contamination when the contamination proportion is unknown. We show that an information-theoretically optimal adaptive confidence set can be constructed by simultaneously quantifying uncertainty across all one-dimensional projections. The resulting confidence set achieves the optimal diameter and reveals a substantial adaptation cost compared with the minimax estimation error. Although statistically optimal, this construction is computationally infeasible. We establish a Statistical Query (SQ) lower bound showing that achieving diameter

O(m^{-1/2})

requires either exponentially many queries or query tolerance

d^{-Ω(m)}

. Thus, in contrast to robust mean estimation, adaptation to the unknown contamination proportion incurs both a statistical cost and a computational barrier within the SQ framework. Finally, we give a low-degree moment-matching algorithm that constructs an adaptive confidence set using

d^{O(m)}

samples and time. Its diameter bound contains an additional

O(m^{-1/2})

term beyond the information-theoretic rate, matching the dependence on

m

in the SQ lower bound. Together, these results characterize the statistical limits of adaptive robust confidence sets under Huber contamination and quantify a computational barrier within the SQ framework.

Ilias Diakonikolas, Chao Gao, Daniel M. Kane +1

University of Wisconsin-Madison · University of Chicago · University of California, San Diego +1

Robust Mean Estimation Low-Degree Polynomial Method Confidence Region Estimation Data Contamination Statistical Learning Theory

Ask PDF

Oct 6, 2026

Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models

We study community recovery in the sparse symmetric stochastic block model with

q

communities, average degree

d

and signal strength

λ

through statistical decision theory and Fisher information, and obtain three characterizations of the Kesten-Stigum threshold

dλ^2=1

and of the information-computation gap below it. First, on each community-size profile the minimax risk of any class of rules closed under averaging and vertex relabeling equals its Bayes risk under the uniform prior; the posterior mean is the unique Bayes rule and is admissible, and the Bayes risk of degree-

D

polynomial rules is the trivial risk times

1-\mathrm{Corr}_D^2

. Combined with known low-degree and information-theoretic results, this gives the gap as a worst-case statement: for

q\ge 5

there is a window below the threshold in which no low-degree rule beats the trivial risk asymptotically, while an exponential-time rule does on a set of labelings of probability

1-o(1)

. Second, the Fisher information about

λ

carried by cycle counts is a series with terms of order

k(dλ^2)^k

, convergent exactly when

dλ^2<1

; below the threshold the relative error of every unbiased cycle-based estimator of

λ^k

stays above an explicit constant, and every cycle-count test has success probability bounded below one. Third, the derivative of belief propagation at its uninformative fixed point multiplies a random perturbation by

|λ|\sqrt{d}

per iteration, and one EM step taken there leaves

λ

unchanged. A signal-to-noise computation recovers the condition

dλ^{1/χ}>1

of Chin et al. for

q=n^χ

communities and identifies personalized PageRank as a walk count with suboptimal weights. Experiments on networks with up to

3\times 10^5

vertices confirm the threshold for

q=2

, the hard window for

q=5

, and the many-community scaling.

Soroor Ghandali

Belief Propagation Low-Degree Polynomial Method Stochastic Block Model Graph Clustering

Ask PDF

Jul 9, 2026

High-Dimensional Procrustes Matching via Tree Counts

Suppose we observe two sets of

n

Gaussian vectors in

\mathbb{R}^d

, with the promise that, after applying a permutation of

[n]

and a rotation of

\mathbb{R}^d

, the two sets are

ρ

-correlated. The Procrustes matching problem asks us to recover the unknown permutation of

[n]

that aligns the two sets. The problem is well-studied in the low-dimensional regime

d=O(\log n)

, but the high-dimensional regime

d\gg \log n

has remained largely uncharted: prior matching guarantees require nearly perfect correlation

ρ=1-o(1)

, even for information-theoretic recovery. Our main result is a polynomial-time algorithm for exact recovery at constant correlation. The algorithm works by computing and comparing weighted counts of a specially chosen family of ``wide'' trees. So long as

d\ge \mathrm{polylog}(n)

, the algorithm succeeds with high probability for any

ρ^2>\sqrtα

, where

α\approx 0.338

is Otter's tree-counting constant. We complement this algorithmic result with an improved information-theoretic guarantee, showing that exact recovery is possible when

ρ^2 \gtrsim \max\{\log n/d,\sqrt{\log n/n}\}

. We also carry out a low-degree advantage calculation, which suggests that the condition

ρ^2 > \sqrtα

is necessary for any tree-counting algorithm.

Xiaochun Niu, Tselil Schramm, Jiaming Xu

The Fuqua School of Business, Duke University, Durham NC, USA · Department of Statistics, Stanford University, Stanford, CA, USA

Orthogonal Procrustes Alignment Low-Degree Polynomial Method

Ask PDF

Jul 9, 2026

Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models

The problem of learning constant-depth circuits holds profound implications for computational learning theory. In a seminal result, by introducing the low-degree algorithm, Linial, Mansour, and Nisan (J. ACM 1993) presented a quasipolynomial-time learner for

\mathsf{AC}^0

under the uniform distribution. However, obtaining comparable learning guarantees for broader classes of correlated distributions has remained a longstanding challenge. Recently, Chandrasekaran, Gaitonde, Moitra, and Vasilyan (arXiv 2026) extended these guarantees to Gibbs distributions on bounded-degree graphical models with both strong spatial mixing and polynomial growth. In this paper, we give a quasipolynomial-time learner for

\mathsf{AC}^0

under graphical models that admit efficient local samplers, circumventing the polynomial-growth requirement in prior work. The key ingredient is a new low-degree approximation for Gibbs distributions, established by simulating and suitably truncating the classical Glauber dynamics. As applications, this framework yields learners for two-spin systems, including the hard-core model and Ising model, on arbitrary bounded-degree graphs, in regimes approaching their respective sampling thresholds.

Weiming Feng, Xiongxin Yang, Yixiao Yu +1

School of Computing and Data Science, The University of Hong Kong. · Department of Computer Science, University of California, Santa Barbara. · State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University.

Boolean Function Learning Low-Degree Polynomial Method

Ask PDF

Jun 15, 2026

Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials

Motivated by the optimization of bounded binary black-box functions, we study the problem of learning polynomial surrogates over the Boolean hypercube. To ensure that optimizing the surrogate yields good solutions for the underlying objective, we require uniform

L_\infty

-error guarantees rather than the usual

L_2

-type guarantees. We characterize the minimax sample complexity of uniform estimation under subgaussian noise for two classes of bounded polynomials. First, for polynomials of degree at most

d

n

variables, the sample complexity scales as

n^{d+1}

. Second, for

s

-sparse Fourier-Walsh polynomials with

s \leq n

, it scales as

ns^2

. These rates differ structurally from the noiseless setting, where uniform exact recovery scales as

n^d

and

ns

, respectively. Our lower bounds hold even for arbitrary adaptive learners, showing that the additional factors are intrinsic to the noisy cases. Standard Fourier-analysis tools for the

L_2

-norm do not naturally extend to the

L_\infty

-setting in a way that yields uniform guarantees. Our proofs overcome this difficulty by relying on suitably chosen auxiliary norms that serve as proxies for controlling the

L_\infty

-error. Together, our results provide a tight characterization of the sample complexity of learning optimization-safe polynomial surrogates.

Jasper van Doornmalen, Mathieu Molina, Victor Verdugo +1

Institute for Mathematical and Computational Engineering, Pontificia Universidad Católica de Chile, Chile · Blavatnik School of Computer Science and AI, Tel Aviv University, Israel · Institute for Mathematical and Computational Engineering, and Department of Industrial and Systems Engineering, Pontificia Universidad Católica de Chile, Chile

Surrogate Modeling Boolean Function Learning Sample Complexity Low-Degree Polynomial Method

Ask PDF

Jun 15, 2026

Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization

A certificate that removes outliers sees the data only through its low-degree moments, and an adversary exploits exactly this, hiding corruption where the clean data already looks typical, in the blind spot no bounded-degree test resolves. That blind spot turns out to have an exact size: the Christoffel function of the clean marginal, the very quantity modern data analysis thresholds to detect outliers, here read from the adversary's side as the corruption a bounded-degree certificate cannot remove. We turn this inversion into the organizing principle of the reweighted-hinge approach to robustly learning

γ

-margin halfspaces under malicious noise (Shen, 2025; Zeng and Shen, 2025): the governing resource is the Sum-of-Squares degree of the outlier-removal certificate, and the resolution principle states that the maximal corruption mass which can hide at a center

c

from a degree-

2t

certificate is exactly the Christoffel function

λ_{t+1}(c)

of the clean marginal. Three consequences follow, all against the certificate method (not information-theoretic). A margin-degree tradeoff: certifying the dense pancake to error

ε

costs SoS degree

Ω(\log(1/ε))

or margin

Ω(\sqrt{\log(1/ε)}/\sqrt{d})

, explaining why the

\log(1/ε)

margin Shen (2025) records is forced, with a weighted-Chebyshev reduction making the threshold

2t=Θ((|c|/s)^2)

tight modulo one classical weighted-extremal estimate. A degree-

2

outlier barrier: the resolution principle realized as an explicit instance on which degree

2

is stuck at

η^{1/2}

while degree

4

escapes, locating the method's small breakdown rate in the degree, not the analysis. And a degree-

2t

algorithm tracing the frontier

η^{1-1/2t}

(recovering Shen (2025) at

t=1

), whose gain is an explicit constant, capped by the pancake density and shown unimprovable by the degree-

2

barrier.

Xiaoyu Li

University of New South Wales

Corruption Robustness Noise Robustness Halfspace Learning Margin-Based Learning Low-Degree Polynomial Method

Ask PDF

Jun 9, 2026

Efficiently Learning Drifting Halfspaces with Massart Noise

We study the problem of learning a drifting concept in the presence of Massart noise. In this framework, an online learner has access to a history of independent samples whose labels are noisy versions of a target concept that may change from round to round. The goal is to output, in each round, a hypothesis with small prediction error. We study the complexity of this learning problem for the fundamental class of margin-separable linear classifiers (halfspaces). On the positive side, we give a computationally efficient learner achieving error

η+ \tilde O(Δ^{1/3}/γ)

, where

η

upper bounds the Massart noise rate,

Δ

is the drift rate, and

γ

is the margin. Interestingly, in the realizable setting, an adaptation of our techniques yields an efficient learner with an improved error rate over prior work. On the lower-bound side, we provide formal evidence of an information-computation tradeoff, strongly suggesting that our algorithm's performance is essentially optimal. Specifically, while the information-theoretically optimal error scales with

Δ^{1/2}

, we prove that

Δ^{1/3}

-scaling is unavoidable for low-degree polynomial tests, even in the special case of random classification noise.

Mingchen Ma, Guyang Cao, Jelena Diakonikolas +1

University of Wisconsin-Madison

Noisy-Label Learning Low-Degree Polynomial Method Learning with Noisy Labels Halfspace Learning Adaptive Learning Margin-Based Learning

Ask PDF

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.

Anda Skeja, Daniel Gutiérrez Espinoza, Fiona Skerman +1

Department of Mathematics, Uppsala University · Department of Mathematics, University of California, Davis

Two-Sample Testing Low-Degree Polynomial Method Graph Clustering Statistical Hypothesis Testing

Ask PDF

May 28, 2026

Quantifying and Optimizing Simplicity via Polynomial Representations

Deep networks often exhibit a preference for "simple" solutions, and such a simplicity bias is widely believed to play a key role in generalization. Yet a broadly applicable, quantitative measure of simplicity remains elusive. We introduce polynomial representations as a distribution-aware, low-dimensional surrogate for neural functions: we approximate a network's predictive behavior along data-dependent interpolation paths using orthogonal polynomial bases, yielding a compact functional representation. We show that the effective degree of this representation serves as a practical simplicity metric that is predictive of generalization across tasks and architectures, and consistently outperforms existing generalization proxies such as sharpness. Finally, polynomial representations naturally yield a differentiable simplicity regularizer, which consistently improves generalization in image and text classification, fine-tuning contrastive vision-language models, and reinforcement learning.

Tianren Zhang, Xiangxin Li, Minghao Xiao +2

Department of Automation, Tsinghua University, Beijing, China.

Neural Network Generalization Low-Degree Polynomial Method

Ask PDF

Apr 7, 2026

Learning $\mathsf{AC}^0$ Under Graphical Models

In a landmark result, Linial, Mansour and Nisan (J. ACM 1993) gave a quasipolynomial-time algorithm for learning constant-depth circuits given labeled i.i.d. samples under the uniform distribution. Their work has had a deep and lasting legacy in computational learning theory, in particular introducing the

\textit{low-degree algorithm}

. However, an important critique of many results and techniques in the area is the reliance on product structure, which is unlikely to hold in realistic settings. Obtaining similar learning guarantees for more natural correlated distributions has been a longstanding challenge in the field. In particular, we give quasipolynomial-time algorithms for learning

\mathsf{AC}^0

substantially beyond the product setting, when the inputs come from any graphical model with polynomial growth that exhibits strong spatial mixing. The main technical challenge is in giving a workaround to Fourier analysis, which we do by showing how new sampling algorithms allow us to transfer statements about low-degree polynomial approximation under the uniform setting to graphical models. Our approach is general enough to extend to other well-studied function classes, like monotone functions and halfspaces.

Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra +1

University of Texas at Austin. · Duke University. · Massachusetts Institute of Technology.

Low-Degree Polynomial Method Boolean Function Learning

Ask PDF

Mar 22, 2026

Gradient Descent with Projection Finds Over-Parameterized Neural Networks for Learning Low-Degree Polynomials with Nearly Minimax Optimal Rate

We study the problem of learning a low-degree spherical polynomial of degree

k_0 = Θ(1) \ge 1

defined on the unit sphere in

\RR^d

by training an over-parameterized two-layer neural network with augmented feature in this paper. Our main result is the significantly improved sample complexity for learning such low-degree polynomials. We show that, for any regression risk

\eps \in (0, Θ(d^{-k_0})]

, an over-parameterized two-layer neural network trained by a novel Gradient Descent with Projection (GDP) requires a sample complexity of

n \asymp Θ( \log(4/δ) \cdot d^{k_0}/\eps)

with probability

1-δ

for

δ\in (0,1)

, in contrast with the representative sample complexity

Θ(d^{k_0} \max\set{\eps^{-2},\log d})

. Moreover, such sample complexity is nearly unimprovable since the trained network renders a nearly optimal rate of the nonparametric regression risk of the order

\log({4}/δ) \cdot Θ(d^{k_0}/{n})

with probability at least

1-δ

. On the other hand, the minimax optimal rate for the regression risk with a kernel of rank

Θ(d^{k_0})

Θ(d^{k_0}/{n})

, so that the rate of the nonparametric regression risk of the network trained by GDP is nearly minimax optimal. In the case that the ground truth degree

k_0

is unknown, we present a novel and provable adaptive degree selection algorithm which identifies the true degree and achieves the same nearly optimal regression rate. To the best of our knowledge, this is the first time that a nearly optimal risk bound is obtained by training an over-parameterized neural network with a popular activation function (ReLU) and algorithmic guarantee for learning low-degree spherical polynomials. Due to the feature learning capability of GDP, our results are beyond the regular Neural Tangent Kernel (NTK) limit.

Yingzhen Yang, Ping Li

School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ 85281, USA · VecML Inc., Bellevue, WA 98004, USA

Low-Degree Polynomial Method Neural Network Generalization Nonparametric Regression Shallow Neural Networks Gradient Projection

Ask PDF

Mar 6, 2026

Agnostic learning in (almost) optimal time via Gaussian surface area

The complexity of learning a concept class under Gaussian marginals in the difficult agnostic model is closely related to its

L_1

-approximability by low-degree polynomials. For any concept class with Gaussian surface area at most

Γ

, Klivans et al. (2008) show that degree

d = O(Γ^2 / \varepsilon^4)

suffices to achieve an

\varepsilon

-approximation. This leads to the best-known bounds on the complexity of learning a variety of concept classes. In this note, we improve their analysis by showing that degree

d = \tilde O (Γ^2 / \varepsilon^2)

is enough. In light of lower bounds due to Diakonikolas et al. (2021), this yields (near) optimal bounds on the complexity of agnostically learning polynomial threshold functions in the statistical query model. Our proof relies on a direct analogue of a construction of Feldman et al. (2020), who considered

L_1

-approximation on the Boolean hypercube.

Lucas Pesenti, Lucas Slot, Manuel Wiedmer

ETH Zurich · University of Amsterdam

Agnostic Learning Statistical Learning Theory Low-Degree Polynomial Method Boolean Function Learning

Ask PDF

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

\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)}

. Moreover, the low-degree moments match exactly up to degree

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.

He Jia, Aravindan Vijayaraghavan

Northwestern University

Low-Degree Polynomial Method

Ask PDF

Feb 27, 2026

Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension

Recent work has shown the surprising power of low-degree sandwiching polynomial approximators in the context of challenging learning settings such as learning with distribution shift, testable learning, and learning with contamination. A pair of sandwiching polynomials approximate a target function in expectation while also providing pointwise upper and lower bounds on the function's values. In this paper, we give a new method for constructing low-degree sandwiching polynomials that yield greatly improved degree bounds for several fundamental function classes and marginal distributions. In particular, we obtain degree

\mathrm{poly}(k)

sandwiching polynomials for functions of

k

halfspaces under the Gaussian distribution, improving exponentially over the prior

2^{O(k)}

bound. More broadly, our approach applies to function classes that are low-dimensional and have smooth boundary. In contrast to prior work, our proof is relatively simple and directly uses the smoothness of the target function's boundary to construct sandwiching Lipschitz functions, which are amenable to results from high-dimensional approximation theory. For low-dimensional polynomial threshold functions (PTFs) with respect to Gaussians, we obtain doubly exponential improvements without applying the FT-mollification method of Kane used in the best previous result.

Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

UT Austin

Low-Degree Polynomial Method Boolean Function Learning

Ask PDF

Feb 26, 2026

Low-degree Lower bounds for clustering in moderate dimension

We study the fundamental problem of clustering

n

points into

K

groups drawn from a mixture of isotropic Gaussians in

\mathbb{R}^d

. Specifically, we investigate the requisite minimal distance

Δ

between mean vectors to partially recover the underlying partition. While the minimax-optimal threshold for

Δ

is well-established, a significant gap exists between this information-theoretic limit and the performance of known polynomial-time procedures. Although this gap was recently characterized in the high-dimensional regime (

n \leq dK

), it remains largely unexplored in the moderate-dimensional regime (

n \geq dK

). In this manuscript, we address this regime by establishing a new low-degree polynomial lower bound for the moderate-dimensional case when

d \geq K

. We show that while the difficulty of clustering for

n \leq dK

is primarily driven by dimension reduction and spectral methods, the moderate-dimensional regime involves more delicate phenomena leading to a "non-parametric rate". We provide a novel non-spectral algorithm matching this rate, shedding new light on the computational limits of the clustering problem in moderate dimension.

Alexandra Carpentier, Nicolas Verzelen

Institut für Mathematik, Universität Potsdam, Germany. · INRAE, MISTEA, Univ. Montpellier, Montpellier, France

Low-Degree Polynomial Method Clustering Gaussian Mixture Models Statistical Learning Theory Information-Theoretic Lower Bounds

Ask PDF