Introduction
The ability of polynomials to approximate continuous functions is a cornerstone of mathematical analysis, dating back to the Weierstrass Approximation Theorem of 1885. In probability theory, this concept is encapsulated by Carleman’s Condition, which determines whether a distribution is uniquely identified by its moments—a property intrinsically linked to the density of polynomials within the distribution's function space.
While the qualitative existence of such approximations is well-established, modern machine learning and algorithmic theory require quantitative guarantees. Specifically, researchers need to know the required polynomial degree $D$ to achieve a target accuracy $\epsilon$. This paper addresses this gap by developing a non-asymptotic version of the classical Denjoy-Carleman theorem, providing a powerful framework for polynomial approximation across a broad range of distributions, including sub-exponential classes.
The Quantitative Gap in Polynomial Approximation
Much of contemporary learning theory relies on the Gaussian distribution due to its convenient orthogonal basis (Hermite polynomials). However, real-world data often follow more general distributions, such as sub-Gaussian or sub-exponential distributions, where explicit bases are unavailable. Without an explicit basis, proving the efficiency of polynomial regression for models like neural networks becomes significantly more difficult.
Existing real-variable proofs for Carleman’s condition often yield "pessimistic" bounds that are practically unusable for complexity analysis. The authors identify that the primary challenge lies in bounding the rate of approximation for general, non-product distributions without relying on specific structural properties of the distribution's basis.
Methodology: A Complex Analytic Approach
To overcome the limitations of real-variable methods, the authors turn to complex analysis. Their approach involves several innovative steps:
- Fourier Interpretation of Residuals: The authors analyze the Fourier transform of the "residual"—the error remaining after projecting a function onto the space of polynomials.
- The "Zero at the Origin" Trick: A fundamental property of orthogonal projections is that the residual is orthogonal to all polynomials up to degree $D$. This implies that the Fourier transform of the weighted residual must possess a "zero of order $D$" at the origin.
- Complex Analytic Scaling: By applying techniques such as conformal mapping (transforming a strip in the complex plane to a unit disk) and the Maximum Modulus Principle, the authors demonstrate that a function with a high-order zero at the origin, which does not grow excessively at infinity, must be extremely small in the neighborhood of the origin.
- Quantitative Denjoy-Carleman Theorem: The authors strengthen the original complex-analytic proof of Carleman’s theorem to provide explicit error rates based on the growth of a distribution's moments.
Key Theoretical Insights
The research yields several transformative insights for approximation theory:
- The Superiority of Complex Analysis: The authors demonstrate that while real-variable methods are mathematically "weak" in this context, viewing the characteristic function in the complex plane allows for rates that are exponentially or even doubly-exponentially better.
- Basis-Free Approximation: The global behavior of the approximation error is controlled by the analyticity of the distribution's moment-generating function, meaning specific orthogonal polynomials are not required to bound the error.
- Universality of Paley-Wiener Classes: Bandlimited functions (those with a maximum frequency) are shown to be universally well-approximated by polynomials across all strictly sub-exponential distributions.
Applications to Learning Theory and Smoothed Analysis
The theoretical framework has immediate implications for machine learning:
- Smoothed Analysis: The paper simplifies the smoothed analysis of learning by showing that the "Gaussian surface area" condition is unnecessary. Instead, low intrinsic dimension is the only structural property required for efficient learning.
- Solving Open Problems: The authors resolve an open problem posed by Chandrasekaran et al. (2024), extending smoothed analysis from Gaussian-like data to heavier-tailed sub-exponential data.
- Neural Network Complexity: The work provides the first quasipolynomial sample complexity bounds for agnostically learning one-layer ReLU and Sigmoid networks over general sub-exponential distributions.
- Optimal Rates for Smooth Functions: For $C^k$ smooth functions, the derived rates match the known tight exponents in classical theory while extending them to unbounded domains.
Conclusion and Future Directions
This work establishes a rigorous bridge between classical complex analysis and modern algorithmic learning theory. While the results in $L^2$ space are robust, future work may extend these findings directly to other $L^p$ norms to yield even tighter constants. Additionally, the massive gap between complex-analytic and real-variable rates remains an intriguing open question. Finally, integrating these results with Sum-of-Squares (SoS) optimization could lead to the development of "testable" learners capable of verifying distributional assumptions in real-time.
Summary updated