Pack only the essentials: Adaptive dictionary learning for kernel ridge regression

• URL: http://arxiv.org/abs/2604.22386v1
• Date: Fri, 24 Apr 2026 09:22:09 GMT
• Title: Pack only the essentials: Adaptive dictionary learning for kernel ridge regression
• Abstract summary: 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.
• Score: 69.32538992633842
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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(n^2) space, which rapidly becomes unfeasible for large n. Nystrom approximations reduce the space complexity to O(nm) by sampling m columns from K_n. Uniform sampling preserves KRR accuracy (up to epsilon) only when m is proportional to the maximum degree of freedom of K_n, which may require O(n) columns for datasets with high coherence. Sampling columns according to their ridge leverage scores (RLS) gives accurate Nystrom approximations with m proportional to the effective dimension, but computing exact RLS also requires O(n^2) space. (Calandriello et al. 2016) propose INK-Estimate, an algorithm that processes the dataset incrementally and updates RLS, effective dimension, and Nystrom approximations on-the-fly. Its space complexity scales with the effective dimension but introduces a dependency on the largest eigenvalue of K_n, which in the worst case is O(n). In this paper we introduce SQUEAK, a new algorithm that builds on INK-Estimate but uses unnormalized RLS. As a consequence, the algorithm is simpler, does not need to estimate the effective dimension for normalization, and achieves a space complexity that is only a constant factor worse than exact RLS sampling.

Related papers

• Adaptive Hybrid Subspace Levenberg Marquardt Algorithm with Adequacy Monitor for Large Scale Least Squares Problems [0.0]
  The Levenberg-Marquardt (LM) algorithm is the most widely used method for solving nonlinear least-squares problems.<n>We propose an adaptive hybrid subspace Levenberg-Marquardt (HSLM) algorithm that constructs a low-dimensional subspace.<n>HSLM achieves convergence behavior comparable to classical and Krylov subspace LM (KSLM) while substantially reducing per-itarity computational cost.
  arXiv  Detail & Related papers  (2026-08-26T08:33:33Z)
• Analysis of Nystrom method with sequential ridge leverage scores [69.32538992633842]
  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.
  arXiv  Detail & Related papers  (2026-04-22T00:49:25Z)
• 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)
• On the Size and Approximation Error of Distilled Sets [57.61696480305911]
  We take a theoretical view on kernel ridge regression based methods of dataset distillation such as Kernel Inducing Points. We prove that a small set of instances exists in the original input space such that its solution in the RFF space coincides with the solution of the original data. A KRR solution can be generated using this distilled set of instances which gives an approximation towards the KRR solution optimized on the full input data.
  arXiv  Detail & Related papers  (2023-05-23T14:37:43Z)
• 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)
• 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)
• Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
  We propose a new formulation for the bundle adjustment problem which relies on nullspace marginalization of landmark variables by QR decomposition. Our approach, which we call square root bundle adjustment, is algebraically equivalent to the commonly used Schur complement trick. We show in real-world experiments with the BAL datasets that even in single precision the proposed solver achieves on average equally accurate solutions.
  arXiv  Detail & Related papers  (2021-03-02T16:26:20Z)
• Faster Kernel Interpolation for Gaussian Processes [30.04235162264955]
  Key challenge in scaling Process (GP) regression to massive datasets is that exact inference requires a dense n x n kernel matrix. Structured kernel (SKI) is among the most scalable methods. We show that SKI can be reduced to O(m log m) after a single O(n) time precomputation step. We demonstrate speedups in practice for a wide range of m and n and apply the method to GP inference on a three-dimensional weather radar dataset with over 100 million points.
  arXiv  Detail & Related papers  (2021-01-28T00:09:22Z)
• Adaptive Explicit Kernel Minkowski Weighted K-means [1.3535770763481905]
  The kernel K-means, which extends K-means into the kernel space, is able to capture nonlinear structures and identify arbitrarily shaped clusters. This paper proposes a method to combine the advantages of the linear and nonlinear approaches by using driven corresponding approximate finite-dimensional feature maps.
  arXiv  Detail & Related papers  (2020-12-04T19:14:09Z)

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.