  We introduce ParK, a new large-scale solver for kernel ridge regression. Our
approach combines partitioning with random projections and iterative
optimization to reduce space and time complexity while provably maintaining the
same statistical accuracy. In particular, constructing suitable partitions
directly in the feature space rather than in the input space, we promote
orthogonality between the local estimators, thus ensuring that key quantities
such as local effective dimension and bias remain under control. We
characterize the statistical-computational tradeoff of our model, and
demonstrate the effectiveness of our method by numerical experiments on
large-scale datasets.
