Constructive Approximation under Carleman's Condition, with Applications to Smoothed Analysis
This work addresses approximation theory and smoothed analysis problems for researchers in mathematical analysis and machine learning, offering incremental advances with new quantitative bounds.
The authors developed a quantitative analogue of the Denjoy-Carleman theorem to control polynomial approximation rates for smooth functions, enabling new L^2 approximation results for general distributions like sub-Gaussian or sub-exponential ones. They applied this to achieve superexponential approximation rates for bandlimited functions and solved an open problem in smoothed analysis of learning with quantitative improvements.
A classical result of Carleman, based on the theory of quasianalytic functions, shows that polynomials are dense in $L^2(μ)$ for any $μ$ such that the moments $\int x^k dμ$ do not grow too rapidly as $k \to \infty$. In this work, we develop a fairly tight quantitative analogue of the underlying Denjoy-Carleman theorem via complex analysis, and show that this allows for nonasymptotic control of the rate of approximation by polynomials for any smooth function with polynomial growth at infinity. In many cases, this allows us to establish $L^2$ approximation-theoretic results for functions over general classes of distributions (e.g., multivariate sub-Gaussian or sub-exponential distributions) which were previously known only in special cases. As one application, we show that the Paley--Wiener class of functions bandlimited to $[-Ω,Ω]$ admits superexponential rates of approximation over all strictly sub-exponential distributions, which leads to a new characterization of the class. As another application, we solve an open problem recently posed by Chandrasekaran, Klivans, Kontonis, Meka and Stavropoulos on the smoothed analysis of learning, and also obtain quantitative improvements to their main results and applications.