Random Feature Stein Discrepancies
This addresses a computational bottleneck for practitioners in fields like Bayesian inference and statistical testing, offering a faster alternative with maintained or improved performance.
The paper tackles the computational inefficiency of existing Stein discrepancies, which grow quadratically in sample size, by introducing feature Stein discrepancies (ΦSDs) and their random approximations (RΦSDs) that are computable in near-linear time. In experiments on sampler selection and goodness-of-fit testing, RΦSDs perform as well or better than quadratic-time methods while being orders of magnitude faster.
Computable Stein discrepancies have been deployed for a variety of applications, ranging from sampler selection in posterior inference to approximate Bayesian inference to goodness-of-fit testing. Existing convergence-determining Stein discrepancies admit strong theoretical guarantees but suffer from a computational cost that grows quadratically in the sample size. While linear-time Stein discrepancies have been proposed for goodness-of-fit testing, they exhibit avoidable degradations in testing power -- even when power is explicitly optimized. To address these shortcomings, we introduce feature Stein discrepancies ($Φ$SDs), a new family of quality measures that can be cheaply approximated using importance sampling. We show how to construct $Φ$SDs that provably determine the convergence of a sample to its target and develop high-accuracy approximations -- random $Φ$SDs (R$Φ$SDs) -- which are computable in near-linear time. In our experiments with sampler selection for approximate posterior inference and goodness-of-fit testing, R$Φ$SDs perform as well or better than quadratic-time KSDs while being orders of magnitude faster to compute.