Exponential inequalities for dependent V-statistics via random Fourier features (Q2184627)

Given a strongly mixing, stationary sequence \(\{X_i\}_{i\in\mathbb{Z}}\) of random variables in \(\mathbb{R}^d\), consider the V-statistic of order \(m\) given by \[ V_n(f)=\sum_{i_1,\ldots,i_m=1}^nf(X_{i_1},\ldots,X_{i_m})\,, \] for some given kernel \(f\). The main results of this paper are non-asymptotic, exponential concentration bounds for these V-statistics. That is, exponential upper bounds on probabilities of the form \[ \mathbb{P}\left(n^{-m}\max_{1\leq k\leq n}\left|\sum_{1\leq i_1,\ldots,i_m\leq k}\left[f(X_{i_1},\ldots,X_{i_m})-\theta\right]\right|\geq x\right)\,, \] for any \(x>0\), where \(\theta\) is an appropriately defined mean. The proofs of these inequalities are based on a kernel expansion which employs random Fourier features. Particular attention is paid to the special case where \(m=2\) and the kernel \(f\) is symmetric and shift-invariant, satisfying \(f(x,y)=f_0(x-y)\) for some function \(f_0\).