Analysis of Nystrom method with sequential ridge leverage scores

2026-04-23 · Source: cs.LG updates on arXiv.org · Field: Technology & Digital — Artificial Intelligence & Machine Learning · Depth: Expert, extended

Summary

This paper introduces INK-Estimate, an algorithm designed for large-scale kernel ridge regression (KRR) in a sequential setting, addressing the computational and memory limitations of traditional Nyström methods. KRR typically requires storing a large kernel matrix, leading to $\mathcal{O}(n^2)$ space and $\mathcal{O}(n^3)$ time complexity for $n$ samples. INK-Estimate maintains a small sketch of the kernel matrix, incrementally updating estimates of ridge leverage scores (RLSs) and the effective dimension in a single pass over the data. This approach requires a fixed, small space budget, $\overline{q}$, proportional to the effective dimension, and provides strong approximation guarantees for the kernel matrix and the statistical risk of the KRR solution at any intermediate step. Unlike prior methods, INK-Estimate's accuracy does not depend on the smallest eigenvalue of the kernel matrix and offers continuous generalization guarantees.

Key takeaway

Research Scientists working with large, evolving datasets for Kernel Ridge Regression should consider INK-Estimate. This algorithm offers a robust, single-pass solution that maintains strong approximation and risk guarantees at every step, unlike traditional batch or online kernel sparsification methods. You can achieve significant computational savings and fixed memory usage, making it suitable for scenarios where continuous, accurate model updates are essential without re-processing historical data.

Key insights

INK-Estimate provides a single-pass, space-efficient sequential Nyström approximation with strong, continuous KRR solution guarantees.

Principles

• RLSs are monotonically decreasing over time.
• Effective dimension is monotonically increasing over time.

Method

INK-Estimate incrementally updates RLS and effective dimension estimates using a Shrink-Expand procedure, maintaining a Nyström approximation with a fixed space budget, and discarding superfluous samples.

In practice

• Use INK-Estimate for online KRR with evolving datasets.
• Apply the algorithm when fixed, small memory footprint is critical.

Topics

• Nyström Method
• Kernel Ridge Regression
• Ridge Leverage Scores
• Sequential Sampling
• INK-Estimate Algorithm

Best for: Research Scientist, AI Scientist

Related on AIssential

• Kernel Two-Sample Testing via Directional Components Analysis — Focusing on well-estimated directional components in RKHS improves kernel two-sample test power and robustness.
• Ridge Regression from Poisson Resetting: A Renewal Perspective on Spectral Regularization — Connecting stochastic resetting to ridge regression offers a renewal perspective on spectral regularization.
• Stein’s method, learning and inference -or- how to really monitor convergence and thin chains — Stein's method, leveraging scores and operators, offers a robust approach for convergence monitoring and advanced probabilistic inference.
• Active Subsampling for Measurement-Constrained M-Estimation of Individualized Thresholds with High-Dimensional Data — Active subsampling significantly accelerates individualized threshold estimation in high-dimensional, label-constrained settings.
• DRIFT: From Robustness Gaps to Invariance Manifolds for AI-Generated Image Detection — AI-generated image detection improves by learning a structured invariance manifold of real images using robust and fragile representation subspaces.
• Heat and Matérn Kernels on Matchings — A framework extends heat and Matérn kernels to matchings, using zonal polynomials for efficient evaluation.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by cs.LG updates on arXiv.org.