Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension

Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

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.

Introduction

In computational learning theory, approximating complex target functions with simpler polynomials is a fundamental task. While standard approximation focuses on minimizing average error, high-stakes scenarios—such as testable learning (where a model must provide a certificate of its performance) or learning with contamination (where data may be adversarially corrupted)—require a more stringent tool: sandwiching polynomials.

A sandwiching pair consists of two polynomials, $p_{up}$ and $p_{down}$, that satisfy the pointwise constraint $p_{down} \leq f \leq p_{up}$ while remaining close to the target function $f$ in expectation. For many geometric concepts, such as the intersection of $k$ halfspaces, previous methods required polynomials of degree exponential in $k$. Since high-degree polynomials are computationally expensive to compute, this has been a major bottleneck in developing efficient, robust learning algorithms.

Methods: The Lipschitz-First Construction

The researchers introduce an elegant two-step "Lipschitz-first" construction that sidesteps the complexities of prior approaches:

  1. Lipschitz Interpolation: Instead of trying to approximate a sharp, discontinuous "step" function (like a halfspace) directly, they first construct two Lipschitz-continuous functions that sandwich the target. This relies on the concept of boundary smoothness—the idea that the decision boundary of the function does not concentrate too much probability mass in its immediate vicinity. By dilating and eroding the target function slightly, they create smooth "buffer zones."
  2. Multivariate Approximation: Once these smooth Lipschitz functions are established, the authors apply a multivariate version of Jackson’s Theorem from high-dimensional approximation theory. Because Lipschitz functions are inherently well-behaved, they can be approximated by polynomials far more efficiently than discontinuous ones.
Geometric representation of boundary regions and buffer zones used in the Lipschitz interpolation step.

This approach focuses on the intrinsic dimension ($k$) of the concept—the number of directions the function actually depends on—rather than the total ambient dimension ($d$) of the data. This shift in perspective allows the bounds to scale with the complexity of the concept itself rather than the data's dimensionality.

Key Results and Improvements

The paper provides massive improvements in the required polynomial degree for several fundamental concept classes under Gaussian and strictly subexponential distributions. Notably, the method avoids the "FT-mollification" technique used in previous state-of-the-art results, leading to a more direct and intuitive proof.

Comparison of degree bounds for various concept classes between this work and prior literature.

As shown in the table above, the improvements are significant:

  • Functions of $k$ Halfspaces: Improved from $2^{O(k)}$ to $\tilde{O}(k^5)$ (Exponential improvement).
  • Intersections of $k$ Halfspaces: Improved from $O(k^6)$ to $\tilde{O}(k^3)$ (Polynomial improvement).
  • Degree-$q$ PTFs: Improved from $\exp(\exp(O(q)))$ to $\tilde{O}(q^6 k^5)$ (Doubly exponential improvement).
  • Convex Sets: Improved from exponential to $\tilde{O}(k^5)$.

Discussion and Future Work

While the $\mathrm{poly}(k)$ bound represents a major leap forward, some non-sandwiching approximation methods achieve $\log(k)$ dependence. A remaining open question is whether the dependence on $k$ in sandwiching polynomials can be further reduced. Additionally, while the current results apply to distributions with subexponential tails, extending this framework to "heavy-tailed" distributions (like those with only a few finite moments) would further enhance the robustness of machine learning models in real-world scenarios.

Summary updated

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.
BibTeX
@misc{klivans2026sandwiching,
  author = {Adam R. Klivans and Konstantinos Stavropoulos and Arsen Vasilyan},
  title = {{Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension}},
  year = {2026},
  eprint = {2602.24178},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.24178},
}

Loading related content...

Figure