The Effective Lasserre's Perturbative Positivstellensatz

We study sum-of-squares (SOS) certificates for nonnegative polynomials $p$ on ${\mathbb{R}}^d$ and their implications for polynomial optimization over unbounded domains. Building on Lasserre’s perturbation approach, we consider SOS representations of $p$ augmented by weighted polynomial tails of the form ${\sum }_{n=0}^N(x\cdot x{)}^n\mathrm{/}(n!{)}^t$ for $0<t<1$. Our main result provides an explicit quantitative bound on the truncation order $N$ required to achieve an $\epsilon$-accurate certificate. Using positivity properties of the Mehler kernel and techniques inspired by polynomial kernel methods, we show that $N$ grows polynomially in $1\mathrm{/}\epsilon$, with rate $N=O((\mathrm{\parallel }p\mathrm{\parallel }\mathrm{/}\epsilon {)}^{1\mathrm{/}(1-t)})$.