Manifold Random Features
This work addresses a foundational challenge in machine learning for approximating kernels on manifolds, offering a new paradigm that could impact various domains, though it builds on existing techniques like Graph Random Features.
The paper tackles the problem of approximating bi-variate functions, such as kernels, on general manifolds by introducing Manifold Random Features (MRFs), which provide positive and bounded features for accurate, low-variance approximation.
We present a new paradigm for creating random features to approximate bi-variate functions (in particular, kernels) defined on general manifolds. This new mechanism of Manifold Random Features (MRFs) leverages discretization of the manifold and the recently introduced technique of Graph Random Features (GRFs) to learn continuous fields on manifolds. Those fields are used to find continuous approximation mechanisms that otherwise, in general scenarios, cannot be derived analytically. MRFs provide positive and bounded features, a key property for accurate, low-variance approximation. We show deep asymptotic connection between GRFs, defined on discrete graph objects, and continuous random features used for regular kernels. As a by-product of our method, we re-discover recently introduced mechanism of Gaussian kernel approximation applied in particular to improve linear-attention Transformers, considering simple random walks on graphs and by-passing original complex mathematical computations. We complement our algorithm with a rigorous theoretical analysis and verify in thorough experimental studies.