Low-Degree Polynomial Method

Follow this topic Ask about this topic

Latest papers

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

Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFs
Nov 3, 2026Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma +2Statistical Learning Theory Low-Degree Polynomial Method
University of Wisconsin-Madison · University of California, San Diego
Low-degree polynomials lower bounds for clustering in small dimension
Oct 27, 2026Alexandra Carpentier, Nicolas VerzelenClustering Gaussian Mixture Models
MISTEA
Adaptive Robust Confidence Sets in High Dimensions
Oct 11, 2026Ilias Diakonikolas, Chao Gao, Daniel M. Kane +1Robust Mean Estimation Low-Degree Polynomial Method
University of Wisconsin-Madison · University of Chicago · University of California, San Diego +1
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
Oct 6, 2026Soroor GhandaliBelief Propagation Low-Degree Polynomial Method
High-Dimensional Procrustes Matching via Tree Counts
Jul 9, 2026Xiaochun Niu, Tselil Schramm, Jiaming XuOrthogonal Procrustes Alignment Low-Degree Polynomial Method
The Fuqua School of Business, Duke University, Durham NC, USA · Department of Statistics, Stanford University, Stanford, CA, USA
Learning $\mathsf{AC}^0$ under Locally Sampleable Graphical Models
Jul 9, 2026Weiming Feng, Xiongxin Yang, Yixiao Yu +1Boolean Function Learning Low-Degree Polynomial Method
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.
Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials
Jun 15, 2026Jasper van Doornmalen, Mathieu Molina, Victor Verdugo +1Surrogate Modeling Boolean Function Learning
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
Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization
Jun 15, 2026Xiaoyu LiCorruption Robustness Noise Robustness
University of New South Wales
Efficiently Learning Drifting Halfspaces with Massart Noise
Jun 9, 2026Mingchen Ma, Guyang Cao, Jelena Diakonikolas +1Noisy-Label Learning Low-Degree Polynomial Method
University of Wisconsin-Madison
Sharp Low-Degree Thresholds for Planted-vs-Planted Testing
Jun 3, 2026Anda Skeja, Daniel Gutiérrez Espinoza, Fiona Skerman +1Two-Sample Testing Low-Degree Polynomial Method
Department of Mathematics, Uppsala University · Department of Mathematics, University of California, Davis
Quantifying and Optimizing Simplicity via Polynomial Representations
May 28, 2026Tianren Zhang, Xiangxin Li, Minghao Xiao +2Neural Network Generalization Low-Degree Polynomial Method
Department of Automation, Tsinghua University, Beijing, China.
Low-Degree Learning from Localization Schemes
Apr 7, 2026Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra +1Low-Degree Polynomial Method Boolean Function Learning
University of Texas at Austin · Duke University · Massachusetts Institute of Technology
Gradient Descent with Projection Finds Over-Parameterized Neural Networks for Learning Low-Degree Polynomials with Nearly Minimax Optimal Rate
Mar 22, 2026Yingzhen Yang, Ping LiLow-Degree Polynomial Method Neural Network Generalization
School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ 85281, USA · VecML Inc., Bellevue, WA 98004, USA
Agnostic learning in (almost) optimal time via Gaussian surface area
Mar 6, 2026Lucas Pesenti, Lucas Slot, Manuel WiedmerAgnostic Learning Statistical Learning Theory
ETH Zurich · University of Amsterdam
Low-Degree Method Fails to Predict Robust Subspace Recovery
Mar 3, 2026He Jia, Aravindan VijayaraghavanLow-Degree Polynomial Method
Northwestern University
Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
Feb 27, 2026Adam R. Klivans, Konstantinos Stavropoulos, Arsen VasilyanLow-Degree Polynomial Method Boolean Function Learning
UT Austin
Low-degree Lower bounds for clustering in moderate dimension
Feb 26, 2026Alexandra Carpentier, Nicolas VerzelenLow-Degree Polynomial Method Clustering
Institut für Mathematik, Universität Potsdam, Germany. · INRAE, MISTEA, Univ. Montpellier, Montpellier, France

Nov 3, 2026J/K move · Enter open · S save

Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFs

Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma, Lisheng Ren+1

University of Wisconsin-Madison · University of California, San Diego

Statistical Learning Theory Low-Degree Polynomial Method

Open paper AskPDF arXiv

We give an algorithm for PAC learning intersections of

k

degree-2 polynomial threshold functions over

R^d

under a Gaussian distribution. Our algorithm achieves classification error

ε

using

d^{O(k)}2^{O_k(\log^3(1/ε))}

time and samples, improving over the

d^{O(k^2/ε^2)}

running time of the polynomial regression approach. To our knowledge, our result is the first to obtain a dimension exponent independent of the accuracy parameter, even for

k=2

. We complement our algorithmic result with an SQ lower bound showing that the complexity dependence of

d^{Ω(k)}

is unavoidable. Lifting the input to polynomial features turns the target into an intersection of

k

halfspaces. This suggests using the first two labeled moments for subspace recovery. In the lifted space, however, these moments can reveal nothing. Our starting point is a Gaussian comparison theorem showing that, for sufficiently regular defining quadratics, the labeled moments needed for subspace recovery are approximately preserved. To handle arbitrary defining quadratics, we establish a new structural result showing that every direction with significant resampling influence can be detected through degree-

O(k)

moments. These results yield an initial

d^{O(k)}2^{\mathrm{poly}_k(1/ε)}

-time learner using adaptive restrictions. To improve the exponential dependence on

1/ε

, we develop a two-stage dimension-reduction approach that avoids the costly adaptive partitioning. After identifying a subspace containing all directions with large influence, we use generalized regularity and Gaussian comparison to recover the remaining relevant quadratic features through a new derivative-based moment operator. The recovered features support an intersection close to the target. Combining them with robust hinge-loss minimization gives our quasipolynomial-time learner.