PaperlayerView exact revision on arXiv

Source-linked AI summary

Analysis of Nystrom method with sequential ridge leverage scores

Daniele Calandriello, Alessandro Lazaric, Michal Valko

arXiv:2604.20077v1cs.LGstat.ML

TL;DR

Large-scale KRR is constrained by the quadratic space needed to store its kernel matrix. INK-Estimate incrementally estimates ridge leverage scores in a one-pass, fixed-space Nyström method. It provides reconstruction and risk guarantees at intermediate steps, although the effective-dimension estimate has spectrum-dependent error.

  • Problem

    Storing the kernel matrix for KRR requires O(n^2) space, limiting its use on large datasets.

    Source: §1 · p. 1

  • Method

    INK-Estimate maintains a Nyström approximation and incrementally updates ridge-leverage-score estimates using the current approximation and each new sample.

    Source: §1 · p. 2

  • Results

    The method provides kernel-approximation and approximate-KRR risk guarantees at every intermediate step, with a fixed space budget scaling with effective dimension.

    Source: §1 · p. 2, §5 · p. 9

  • Takeaways & Limitations

    The guarantees allow the algorithm to return an accurate intermediate solution or be interrupted at any time.

    Source: §1 · p. 2

    The approximate effective-dimension error scales with the matrix spectrum through coefficient ρ, and its influence on space and time complexity can vary significantly.

    Source: §5 · p. 9, §4.3 · p. 9

Abstract

from arXiv · show

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.

1 INTRODUCTION

Kernel ridge regression becomes difficult at scale because storing its kernel matrix requires quadratic space, while existing Nyström and online methods face tradeoffs in sampling quality, passes, or guarantees. INK-Estimate incrementally tracks ridge leverage scores in one pass and provides fixed-space approximation and risk guarantees at every step.

1 INTRODUCTION

  • Storing the KRR matrix requires O(n^2) space, motivating methods that reduce memory while retaining accurate solutions.This challenge applies to both batch and online KRR as dataset size grows.Source: §1 · p. 1
  • Ridge-leverage-score sampling can approximate relevant kernel directions using a number of columns proportional to effective dimension, but exact scores cost as much as solving KRR.Approximate scores can retain strong guarantees, though the cited prior approach requires multiple data passes and has error bounds inversely dependent on the minimum eigenvalue.Source: §1 · pp. 1–2
  • Prior online kernel sparsification selects dictionary samples using correlation criteria, while its analyzed guarantees can depend on empirical error or eigenvalue-decay assumptions.Some methods cannot remove selected samples, and sequential KRR needs guarantees at intermediate steps as well as at the endpoint.Source: §1 · p. 2
  • INK-Estimate processes the dataset in one pass, maintaining a Nyström approximation and updating ridge-leverage-score estimates from the approximation and each new sample.Its fixed space budget is proportional to effective dimension and the required accuracy.Source: §1 · p. 2
  • The method provides reconstruction and approximate-KRR risk guarantees at every intermediate step, without assumptions on the regularization parameter or minimum eigenvalue.Its space budget scales with average rather than maximum degrees of freedom; the introduction also contrasts its exact-KRR guarantees with other online methods.Source: §1 · p. 2

2 BACKGROUND

The background defines exact kernel ridge regression and motivates Nyström approximation as a way to reduce its computational and storage burden. It then describes ridge-leverage-score sampling and its reconstruction and risk guarantees, setting up the sequential method.

2.1 Exact Kernel Ridge Regression

  • Exact KRR computes a regularized solution from the kernel matrix, but its computation requires O(n^3) time and O(n^2) space.The paper measures fixed-design accuracy by prediction error on the dataset.Source: §2.1 · p. 3

2.2 Nyström Approximation with Ridge Leverage Scores

  • Nyström approximation samples weighted kernel-matrix columns to form a low-rank approximation, reducing storage from O(n^2) to O(nm) and computation to O(nm^2 + m^3).The approximate solution is obtained by replacing the full kernel matrix in the regularized problem with its approximation.Source: §2.2 · p. 3
  • Ridge leverage scores measure column relevance to regularized regression, and their sum is the effective dimension used to define the sampling distribution.The regularization parameter acts as a soft threshold on kernel-matrix rank.Source: §2.2 · p. 4
  • With the stated sampling budget, batch Nyström approximation provides a kernel-reconstruction bound and an approximate solution whose prediction error is at most a factor (1 + 2ε)^2 from the exact solution when γ is properly tuned.The approximation error is bounded by γ/(1 − ε).Source: §2.2 · p. 4
  • Exact ridge leverage scores are as hard to compute as solving regression, and a prior two-pass approximation has error dependent on the minimum eigenvalue.The paper motivates an incremental approach that avoids dependence on a large minimum eigenvalue and on a small maximum ridge leverage score.Source: §2.2 · pp. 4–5

3 INCREMENTAL ORACLE KERNEL APPROXIMATION WITH SEQUENTIAL SAMPLING

This section develops sequential RLS-based Nyström sampling despite changing scores and effective dimension, while the dictionary must admit and discard columns. INK-Oracle updates the approximation incrementally and analyzes its quality and space use across the stream.

3 INCREMENTAL ORACLE KERNEL APPROXIMATION WITH SEQUENTIAL SAMPLING

  • Sequential sampling must track changing RLSs and effective dimension, while revising the dictionary because dropped columns cannot be sampled again.The section frames these as concurrent challenges to extending RLS sampling to the sequential setting.Source: §3 · p. 5

3.1 The INK-Oracle Algorithm

  • INK-Oracle takes approximate RLS-based probabilities, caps each at its previous value, then shrinks existing weights and expands for the new column.A new column can be discarded in the same iteration it arrives, and dropped columns are not queried again.Source: §3.1 · p. 6

3.2 Analysis of INK-Oracle

  • With probability 1−δ, INK-Oracle satisfies Eq. 11’s Nyström approximation bound for all t, while its random column count is within a constant factor of q with high probability.The analysis also shows the method matches the batch counterpart’s guarantees when q is large enough.Source: §3.2 · pp. 6–7
  • The space budget scales with effective dimension, controls dictionary size at every step, and permits automatic removal of superfluous old samples without a spectrum assumption.The budget may need adjustment if the problem’s actual complexity exceeds what the user can afford.Source: §3.2 · p. 6
  • True sampling probabilities decrease over time; taking the minimum of successive approximate probabilities preserves the oracle approximation while enforcing that decrease.The analysis uses this monotonicity to support the shrink step and its column-count bound.Source: §3.2 · p. 7

4 LEVERAGE SCORES AND EFFECTIVE DIMENSION ESTIMATION

Section 4 constructs the incremental RLS and effective-dimension estimators needed by INK-Estimate, then analyzes the resulting algorithm. Its guarantees hold at every step, while the effective-dimension error and resource requirements can depend on the kernel spectrum.

4.1 Leverage Scores

  • The RLS estimator uses stored exact columns and the new column with the smaller approximation for inversion, yielding an α-approximation independent of the smallest eigenvalue.It estimates scores only for dictionary columns and the newly arrived column.Source: §4.1 · pp. 7–8

4.2 Effective Dimension

  • The effective-dimension estimator updates the increment of the aggregate score without retrieving absent columns, but its approximation error β depends on the spectrum.The increment estimate uses the current approximation and the new column and scalar.Source: §4.2 · p. 8

4.3 Analysis of INK-Estimate

  • With probability 1−δ, INK-Estimate’s Nyström approximation satisfies the stated kernel-matrix error bound at every t, and its KRR solution inherits Batch-Exact’s approximation and risk guarantees.The analysis also bounds the algorithm’s space and time complexity.Source: §4.3 · pp. 8–9
  • When λmax grows without a matching increase in γ, space and time requirements can grow even as the risk bound remains small; increasing γ alone weakens risk guarantees.The spectrum affects β through the ρ coefficient.Source: §4.3 · p. 9

5 CONCLUSION

The paper presents a single-pass sequential Nyström method whose approximation and risk guarantees hold at every intermediate step. Its effective-dimension error depends on the spectrum, and its generalization results are limited to fixed design.

5 CONCLUSION

  • The sequential Nyström algorithm constructs an approximate kernel matrix and KRR solution in one pass, with guarantees valid for every intermediate matrix.The approximate solution’s risk is close to that of the exact solution.Source: §5 · p. 9
  • Separate incremental estimators approximate RLSs and effective dimension multiplicatively, but the effective-dimension error scales with the spectrum through ρ.The authors note that a sharper analysis or different estimator might improve this dependence.Source: §5 · p. 9
  • Generalization results apply to fixed design; random-design extension requires careful regularization tuning, and the runtime analysis does not fully exploit sequential updates.Update-friendly decompositions or hot-start low-rank solvers might improve runtime.Source: §5 · p. 9

A Extended proofs of Section 3

The extended proofs analyze the evolution of RLSs and effective dimension separately. They use kernel bordering and matrix identities to establish the intermediate results and combine them in a lemma.

A Extended proofs of Section 3

B Proof of Theorem 1 and 2

The appendix proves Theorems 1 and 2 by analyzing the algorithm’s random weight updates and dictionary size. It uses martingale concentration and a separate bound on surviving columns.

B Proof of Theorem 1 and 2

  • The proof bounds the matrix process using Freedman’s inequality and applies a Chernoff bound to its predictable quadratic variation.Source: B Proof of Theorem 1 and 2 · pp. 14–16
  • Conditioned on the past, the approximate probabilities are fixed and the randomized weight update has expected value equal to its preceding weight.This establishes the martingale property used in the proof.Source: B Proof of Theorem 1 and 2 · p. 15
  • Dictionary size is analyzed by counting surviving columns with indicator variables whose probabilities are bounded by the inclusion probabilities.The passage states that the survival indicators are independent Bernoulli variables.Source: B Proof of Theorem 1 and 2 · p. 18

C Extended proofs of Section 4

The extended proofs derive incremental approximation guarantees using matrix bounds and induction. The effective-dimension approximation is carried forward from an exactly computed initial value.

C Extended proofs of Section 4

  • The Lemma 2 argument uses block-matrix multiplication and bounds to show that the updated kernel matrix satisfies condition (11).Source: C Extended proofs of Section 4 · p. 19
  • The estimator approximates leverage scores only for fully stored columns, avoiding access to K^1/2 because computing it would take too much time and space.Source: C Extended proofs of Section 4 · pp. 19–20
  • The proof of Lemma 3 establishes the effective-dimension approximation by bounding the update and applying induction from an exactly computed initial value.The induction shows the estimate at time t+1 remains a β-approximation.Source: C Extended proofs of Section 4 · pp. 20, 22
  • At each update, the estimated and true effective dimensions add their respective increments, preserving the β-approximation at time t+1.Source: C Extended proofs of Section 4 · p. 22
Loading 2604.20077v1…