# Local optimisation of Nystr"om samples through stochastic gradient descent

arXiv: https://arxiv.org/abs/2203.13284 · HTML: https://mlsanity.com/paper/2203.13284/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 18 references that are in the map.
- First posted on arXiv 24 Mar 2022.

## Builds on (most cited first, 3 of 3)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)

## Abstract (arXiv)

We study a relaxed version of the column-sampling problem for the Nystr"om approximation of kernel matrices, where approximations are defined from multisets of landmark points in the ambient space; such multisets are referred to as Nystr"om 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"om approximation accuracy; in this setting, we discuss how Nystr"om 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"om samples with improved Nystr"om approximation accuracy.