Optimal Convergence Rates for Distributed Nystrom Approximation

The distributed kernel ridge regression (DKRR) has shown great potential in processing complicated tasks. However, DKRR only made use of the local samples that failed to capture the global characteristics. Besides, the existing optimal learning guarantees were provided in expectation and only pertain to the attainable case that the target regression lies exactly in the kernel space. In this paper, we propose distributed learning with globally-shared Nystro center dot m centers (DNystro center dot m), which utilizes global information across the local clients. We also study the statistical properties of DNystro center dot m in expectation and in probability, respectively, and obtain several state-of-the-art results with the minimax optimal learning rates. Note that, the optimal convergence rates for DNystro center dot m pertain to the non-attainable case, while the statistical results allow more partitions and require fewer Nystro center dot m centers. Finally, we conduct experiments on several real-world datasets to validate the effectiveness of the proposed algorithm, and the empirical results coincide with our theoretical findings.

Automated summary

This paper proposes a distributed learning method DNystro center dot m with globally-shared Nystro center dot m centers, which improves the limitations of DKRR in processing complicated tasks by utilizing global information. The statistical properties of DNystro center dot m in expectation and in probability are studied, and state-of-the-art results with the minimax optimal learning rates are obtained.