Analysis of Nystrom method with sequential ridge leverage scores

• URL: http://arxiv.org/abs/2604.20077v1
• Date: Wed, 22 Apr 2026 00:49:25 GMT
• Title: Analysis of Nystrom method with sequential ridge leverage scores
• Abstract summary: Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix K_t.<n>Recent works show that a sampling distribution proportional to the ridge leverage scores (RLSs) provides strong reconstruction guarantees for the approximation.<n>We introduce the INK-ESTIMATE algorithm, that incrementally computes the RLSs estimates.
• Score: 69.32538992633842
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix K_t. To avoid storing the entire matrix K_t, Nystrom methods subsample a subset of columns of the kernel matrix, and efficiently find an approximate KRR solution on the reconstructed matrix. The chosen subsampling distribution in turn affects the statistical and computational tradeoffs. For KRR problems, recent works show that a sampling distribution proportional to the ridge leverage scores (RLSs) provides strong reconstruction guarantees for the approximation. While exact RLSs are as difficult to compute as a KRR solution, we may be able to approximate them well enough. In this paper, we study KRR problems in a sequential setting and introduce the INK-ESTIMATE algorithm, that incrementally computes the RLSs estimates. INK-ESTIMATE maintains a small sketch of K_t, that at each step is used to compute an intermediate estimate of the RLSs. First, our sketch update does not require access to previously seen columns, and therefore a single pass over the kernel matrix is sufficient. Second, the algorithm requires a fixed, small space budget to run dependent only on the effective dimension of the kernel matrix. Finally, our sketch provides strong approximation guarantees on the distance between the true kernel matrix and its approximation, and on the statistical risk of the approximate KRR solution at any time, because all our guarantees hold at any intermediate step.

Related papers

• Pack only the essentials: Adaptive dictionary learning for kernel ridge regression [69.32538992633842]
  One of the major limits of kernel ridge regression (KRR) is that storing and manipulating the kernel matrix K_n for n samples requires O(n2) space.<n>INK-Estimate is an algorithm that processes the dataset incrementally and updates RLS, effective dimension, and Nystrom approximations on-the-fly.<n>In this paper we introduce SQUEAK, a new algorithm that builds on INK-Estimate but uses unnormalized RLS.
  arXiv  Detail & Related papers  (2026-04-24T09:22:09Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Robust Kernel Sparse Subspace Clustering [0.0]
  We propose for the first time robust kernel sparse SC (RKSSC) algorithm for data with gross sparse corruption. The concept, in principle, can be applied to other SC algorithms to achieve robustness to the presence of such type of corruption.
  arXiv  Detail & Related papers  (2024-01-30T14:12:39Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Robust, randomized preconditioning for kernel ridge regression [4.633920223660256]
  It describes two methods with the strongest guarantees available for kernel ridge regression problems.<n>The proposed methods efficiently solve a range of KRR problems, making them well-suited for practical applications.
  arXiv  Detail & Related papers  (2023-04-24T21:48:24Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  We propose a novel algorithm that uses a random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel. Our algorithm provides at least a 100-fold speedup over KIP and can run on a single GPU. Our new method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms in accuracy over a range of large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-21T15:56:13Z)
• Target alignment in truncated kernel ridge regression [12.139222986297264]
  We study how the alignment between the target function and the kernel affects the performance of the Kernel ridge regression (KRR) We show that for alignment, there is an emphover-aligned regime, in which TKRR can achieve a faster rate than what is achievable by full KRR. We also consider the bandlimited alignment setting and show that the regularization surface of TKRR can exhibit transient effects including multiple descent and non-monotonic behavior.
  arXiv  Detail & Related papers  (2022-06-28T19:16:10Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  Existing implementations of KRR require that all the data is stored in the main memory. We propose StreaMRAK - a streaming version of KRR. We present a showcase study on two synthetic problems and the prediction of the trajectory of a double pendulum.
  arXiv  Detail & Related papers  (2021-08-23T21:03:09Z)
• Fast Statistical Leverage Score Approximation in Kernel Ridge Regression [12.258887270632869]
  Nystr"om approximation is a fast randomized method that rapidly solves kernel ridge regression (KRR) problems. We propose a linear time (modulo poly-log terms) algorithm to accurately approximate the statistical leverage scores in the stationary- Kernel-based KRR.
  arXiv  Detail & Related papers  (2021-03-09T05:57:08Z)
• SimpleMKKM: Simple Multiple Kernel K-means [49.500663154085586]
  We propose a simple yet effective multiple kernel clustering algorithm, termed simple multiple kernel k-means (SimpleMKKM) Our criterion is given by an intractable minimization-maximization problem in the kernel coefficient and clustering partition matrix. We theoretically analyze the performance of SimpleMKKM in terms of its clustering generalization error.
  arXiv  Detail & Related papers  (2020-05-11T10:06:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.