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.

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.
Learning $\mathsf{AC}^0$ Under Graphical Models
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

Oct 11, 2026J/K move · Enter open · S save

Adaptive Robust Confidence Sets in High Dimensions

Ilias Diakonikolas, Chao Gao, Daniel M. Kane, Yuetian Luo

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

Open paper AskPDF arXiv

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.