Constructive Approximation under Carleman's Condition, with Applications to Smoothed Analysis

A classical consequence of Carleman’s condition is that polynomials are dense in L2(µ), but qualitative density does not quantify the degree needed for approximation over general noncompact measures. We give a basis-free Fourier-analytic framework in which orthogonality of the degree-D residual forces a zero of order D in its transformed residual, and analyticity of the moment generating function turns that zero into explicit approximation rates. In the two regimes used in this proceedings version, this yields superexponential low-frequency decay under strictly sub-exponential inputs and tanh(cΩ)D decay under sub-exponential inputs. These two formulas are concrete special cases of a broader quantitative Denjoy–Carleman principle under Carleman’s condition, whose full logarithmic-integral form is deferred to the full version. As an application, we show that Gaussian smoothing, intrinsic-dimension reduction, and low-degree polynomial regression together give low-degree approximation guarantees for smoothed low-intrinsic-dimensional targets. This lets us solve the sub-exponential case of smoothed agnostic learning left open by Chandrasekaran, Klivans, Kontonis, Meka, and Stavropoulos, while removing the Gaussian surface area assumption in the strictly sub-exponential setting.