Local optimisation of Nyström samples through stochastic gradient descent
This work addresses a specific computational bottleneck in kernel methods for machine learning, but it is incremental as it builds on existing Nyström approximation techniques.
The paper tackles the problem of optimizing Nyström samples for kernel matrix approximation by using stochastic gradient descent to minimize a radial squared-kernel discrepancy criterion, resulting in improved approximation accuracy as demonstrated in numerical experiments.
We study a relaxed version of the column-sampling problem for the Nyström approximation of kernel matrices, where approximations are defined from multisets of landmark points in the ambient space; such multisets are referred to as Nyström samples. We consider an unweighted variation of the radial squared-kernel discrepancy (SKD) criterion as a surrogate for the classical criteria used to assess the Nyström approximation accuracy; in this setting, we discuss how Nyström samples can be efficiently optimised through stochastic gradient descent. We perform numerical experiments which demonstrate that the local minimisation of the radial SKD yields Nyström samples with improved Nyström approximation accuracy.