Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension

Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:3993-4021, 2026.

Abstract

Recent work has shown the surprising power of low-degree {\em 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 \emph{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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-klivans26a, title = {Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension}, author = {Klivans, Adam and Stavropoulos, Konstantinos and Vasilyan, Arsen}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {3993--4021}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/klivans26a/klivans26a.pdf}, url = {https://proceedings.mlr.press/v336/klivans26a.html}, abstract = { Recent work has shown the surprising power of low-degree {\em 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 \emph{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.} }
Endnote
%0 Conference Paper %T Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension %A Adam Klivans %A Konstantinos Stavropoulos %A Arsen Vasilyan %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-klivans26a %I PMLR %P 3993--4021 %U https://proceedings.mlr.press/v336/klivans26a.html %V 336 %X Recent work has shown the surprising power of low-degree {\em 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 \emph{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.
APA
Klivans, A., Stavropoulos, K. & Vasilyan, A.. (2026). Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:3993-4021 Available from https://proceedings.mlr.press/v336/klivans26a.html.

Related Material