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

Authors	Lucas Pesenti et al.
Year	2026
Field	Machine Learning
arXiv	2603.06027
PDF	Download
Categories	cs.LG, cs.DS, stat.ML

Abstract

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.

---

Engineering Breakdown

Plain English

This paper addresses a fundamental problem in machine learning: how efficiently can we learn concepts from data in the agnostic setting (where no perfect hypothesis exists) when features follow a Gaussian distribution? The authors improve the polynomial degree required to achieve epsilon-approximation from O(Γ²/ε⁴) down to Õ(Γ²/ε²), where Γ is the Gaussian surface area of the concept class. This improvement is significant because it matches known lower bounds from prior work, meaning their solution is nearly optimal. The result has direct implications for learning polynomial threshold functions in the statistical query model, which is a restricted but practically important setting for understanding learning complexity.

Core Technical Contribution

The key innovation is a refined analysis technique that tightens the relationship between Gaussian surface area and polynomial approximation. While Klivans et al. (2008) showed that degree d = O(Γ²/ε⁴) suffices, this paper proves that degree d = Õ(Γ²/ε²) is actually enough—a quadratic improvement in the ε dependence. The improvement comes from a more direct argument that avoids looseness in the previous reduction. Critically, the authors demonstrate that their bound aligns with the Ω(Γ²/ε²) lower bounds established by Diakonikolas et al. (2021), proving near-optimality of their approach and closing a significant gap in the theoretical understanding of agnostic learning.

How It Works

The approach centers on approximating a concept class using low-degree polynomials under Gaussian marginals. Given a concept class with Gaussian surface area Γ, the algorithm constructs a polynomial approximation of degree d that minimizes the L₁ approximation error to ε. The paper's technical contribution is a direct proof that leverages properties of Gaussian measure and polynomial approximation theory to show fewer polynomial terms are needed than previously thought. The mechanism works by carefully analyzing how the surface area bounds the approximation error when using degree-d polynomials, avoiding intermediate steps that introduced polynomial factors in ε. The input is a concept class and error tolerance ε; the output is a degree d and a corresponding polynomial that approximates the class. The proof technique provides explicit polynomial degree bounds that can be instantiated for specific concept classes like polynomial threshold functions.

Production Impact

For engineers building learning systems, this work provides tighter theoretical guarantees on sample complexity and computational resources needed for agnostic learning tasks. If you're implementing learners for concepts under Gaussian assumptions (common in signal processing and some classification tasks), you now have stronger worst-case bounds on the polynomial degree your approximator needs—potentially reducing model complexity and training time by eliminating unnecessary polynomial terms. The statistical query model results are particularly relevant for differentially private learning systems, where SQ algorithms are mandatory; the improved bounds translate directly to fewer queries needed to achieve target accuracy. However, the impact is primarily theoretical—you'd need to verify empirically that these degree bounds are tight for your specific problem, as asymptotic improvements may not manifest at practical problem scales. The main trade-off is implementation complexity: leveraging these results requires careful polynomial construction and may add engineering overhead compared to simpler approximation schemes.

Limitations and When Not to Use This

This paper assumes Gaussian marginal distributions on features, which is restrictive and often violated in real-world datasets where features have heavy tails, discrete structure, or non-standard distributions. The analysis applies to the agnostic model where the true label may be arbitrarily corrupted; this differs from the benign setting and doesn't directly give you accuracy guarantees when your data satisfies stronger assumptions. The bounds are asymptotic and involve Õ notation (hiding poly-logarithmic factors), so the constant factors and logarithmic terms could be prohibitively large for moderate ε and Γ values in practice. Additionally, the paper focuses on statistical complexity (sample size and polynomial degree) but provides limited algorithmic guidance on efficiently constructing or evaluating the polynomials—there may be a significant gap between theoretical learnability and computational tractability. The near-optimality result relies on matching specific lower bounds from prior work; extending this to other settings (non-Gaussian distributions, other concept classes) remains open.

Research Context

This work builds directly on the polynomial learning framework of Klivans et al. (2008) and is motivated by closing gaps identified by Diakonikolas et al. (2021) on lower bounds for agnostic learning. The paper sits at the intersection of computational learning theory and harmonic analysis on Gaussian spaces, connecting classical approximation theory to modern learning-theoretic questions. The results are particularly relevant for the statistical query (SQ) model community, which uses Gaussian analysis to derive query complexity lower bounds; this work shows those bounds are achievable. The research advances fundamental understanding of the role surface area plays in learning and may inspire tighter analyses in other settings (e.g., log-concave distributions) where similar surface-area-based arguments apply.

---

:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::

---

Back to Research Lab → · Subscribe to AI Letters →