The paper proves exponential concentration for random Fourier kernel estimates. For a fixed pair, the stated tail bound is Pr(|z(x)'z(y)-k(x,y)| >= epsilon) <= 2 exp(-D epsilon^2/2). Uniformly over a compact M, Claim 1 bounds the failure probability by 2^8 (sigma_p diam(M)/epsilon)^2 exp(-D epsilon^2/[4(d+2)]), and states that constant-probability uniform error at most epsilon follows for D = Omega((d/epsilon^2) log(sigma_p diam(M)/epsilon)). · CiteArk
The paper proves exponential concentration for random Fourier kernel estimates. For a fixed pair, the stated tail bound is Pr(|z(x)'z(y)-k(x,y)| >= epsilon) <= 2 exp(-D epsilon^2/2). Uniformly over a compact M, Claim 1 bounds the failure probability by 2^8 (sigma_p diam(M)/epsilon)^2 exp(-D epsilon^2/[4(d+2)]), and states that constant-probability uniform error at most epsilon follows for D = Omega((d/epsilon^2) log(sigma_p diam(M)/epsilon)).
来源：paper:PDF p. 3, Section 3, Claim 1; proof on PDF p. 8, Eqs. (5)-(7)
