  We propose two algorithms for boosting random Fourier feature models for
approximating high-dimensional functions. These methods utilize the classical
and generalized analysis of variance (ANOVA) decomposition to learn low-order
functions, where there are few interactions between the variables. Our
algorithms are able to find an index set of important input variables and
variable interactions reliably. Furthermore, we generalize already existing
random Fourier feature models to an ANOVA setting, where terms of different
order can be used. Our algorithms have the advantage of interpretability,
meaning that the influence of every input variable is known in the learned
model, even for dependent input variables. We give theoretical as well as
numerical results that our algorithms perform well for sensitivity analysis.
The ANOVA-boosting step reduces the approximation error of existing methods
significantly.
