Parallelizing Spectral Algorithms for Kernel Learning
This work addresses the problem of scaling kernel learning algorithms for large datasets, offering a distributed approach that maintains statistical efficiency, though it is incremental as it builds on classical methods.
The paper tackles the computational challenge of applying spectral regularization methods in kernel learning by partitioning data into subsets, applying regularization on each, and averaging results, achieving a substantial reduction in computation time while preserving minimax optimal convergence rates under certain conditions.
We consider a distributed learning approach in supervised learning for a large class of spectral regularization methods in an RKHS framework. The data set of size n is partitioned into $m=O(n^α)$ disjoint subsets. On each subset, some spectral regularization method (belonging to a large class, including in particular Kernel Ridge Regression, $L^2$-boosting and spectral cut-off) is applied. The regression function $f$ is then estimated via simple averaging, leading to a substantial reduction in computation time. We show that minimax optimal rates of convergence are preserved if m grows sufficiently slowly (corresponding to an upper bound for $α$) as $n \to \infty$, depending on the smoothness assumptions on $f$ and the intrinsic dimensionality. In spirit, our approach is classical.