Randomized sketches for sparse additive models

Sparse additive models in the setting of reproducing kernel Hilbert spaces have theoretically optimal properties even in high dimensions. However, its computational cost is heavy, especially considering that it contains two regularization parameters associated with different norms. In the big data setting, fitting of the model becomes infeasible. As our first attempt to address this issue, we herein consider fixed-dimensional setting and propose a randomized sketches approach for sparse additive models. It is shown that the sketched estimator has the same optimal convergence rate as the standard estimator. Some Monte Carlo examples are presented to illustrate the performance of the estimators.