Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension

Adam R. Klivans; Konstantinos Stavropoulos; Arsen Vasilyan

cs.LGFeb 27, 2026

Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension

Authors: Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

Organizations: UT Austin

Abstract

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.

Figures & tables

Concept Class	This Work	Prior Work	References
Intersections of $k$ Halfspaces	${\widetilde{O}(k^{3})}$	${{{{O}}(k^{6})}}$	[ 29 ]
Functions of $k$ Halfspaces	${\widetilde{O}(k^{5})}$	${\exp{{{O}}(k)}}$	[ 29 ] [ 37 ] [ 26 ]
Convex Sets in $k$ dimensions	${\widetilde{O}(k^{5})}$	None $\ast$	[ 14 ]
Degree- $q$ PTFs in $k$ dimensions	${\widetilde{O}(q^{6}k^{5})}$	${\exp\exp{{{{O}}(q)}}}$ or worse $\dagger$	[ 33 ] [ 58 ]
Functions of $t$ concepts each with intrinsic dimension $k$ and $\sigma$ -smooth boundary $\ddagger$	${\widetilde{O}(\sigma^{2}t^{5}k^{3})}$	None	–

Table 1: Comparison between upper bounds from this work and the best known bounds in previous work on the

(\epsilon=0.1,s=O(1))

-sandwiching degree of various geometric concept classes with respect to the standard Gaussian distribution.

Figure 1: Our upper sandwiching polynomial for $f_{\mathrm{up}}$ is of the form $p_{\mathrm{up}}=p_{1}(\mathbf{x})+p_{2}(\mathbf{x})+\epsilon$ . In region $\mathcal{X}_{1}$ , $p_{1}$ is a pointwise $\epsilon$ -approximator for $f_{\mathrm{up}}$ and $0\leq p_{2}(\mathbf{x})\leq\epsilon$ , so $f_{\mathrm{up}}(\mathbf{x})\leq p_{\mathrm{up}}(\mathbf{x})\leq f_{\mathrm{up}}(\mathbf{x})+3\epsilon$ . In region $\mathcal{X}_{2}$ , $p_{1}$ is still an pointwise $\epsilon$ -approximator for $f_{\mathrm{up}}$ and $p_{2}(\mathbf{x})>0$ , so $f_{\mathrm{up}}(\mathbf{x})\leq p_{1}(\mathbf{x})+\epsilon\leq p_{\mathrm{up}}(\mathbf{x})$ . In region $\mathcal{X}_{3}$ we have $p_{2}(\mathbf{x})\geq 1+|p_{1}(\mathbf{x})|\geq f_{\mathrm{up}}(\mathbf{x})+|p_{1}(\mathbf{x})|$ , so $p_{\mathrm{up}}(\mathbf{x})\geq f_{\mathrm{up}}(\mathbf{x})$ .

Low-Degree Polynomial Method

See all 15 papers

May 8, 2026

A Note on Non-Negative $L_1$ -Approximating Polynomials

L_1

-Approximating polynomials, i.e., polynomials that approximate indicator functions in

L_1

-norm under certain distributions, are widely used in computational learning theory. We study the existence of non-negative

L_1

-approximating polynomials with respect to Gaussian distributions. This is a stronger requirement than

L_1

-approximation but weaker than sandwiching polynomials (which themselves have many applications). These non-negative approximating polynomials have recently found uses in smoothed learning from positive-only examples. In this short note, we prove that every class of sets with Gaussian surface area (GSA) at most

Γ

under the standard Gaussian admits degree-

k

non-negative polynomials that

\eps

-approximate its indicator functions in

L_1

-norm, for

k=\tilde{O}(Γ^2/\varepsilon^2)

. Equivalently, finite GSA implies

L_1

-approximation with the stronger pointwise guarantee that the approximating polynomial has range contained in

[0,\infty)

. Up to a constant-factor, this matches the degree of the best currently known Gaussian

L_1

-approximation degree bound without the non-negativity constraint.

Jane H. Lee, Anay Mehrotra, Manolis Zampetakis

Yale University · Stanford University

Statistical Learning Theory

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

Abstract

Low-Degree Polynomial Method

Explore similar work

A Note on Non-Negative L1L_1L1​-Approximating Polynomials

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

Low-Degree Method Fails to Predict Robust Subspace Recovery

A Note on Non-Negative $L_1$ -Approximating Polynomials