Analysis of Nystrom method with sequential ridge leverage scores

Large-scale kernel ridge regression (KRR) is limited by storing and manipulating large kernel matrices, and this paper introduces an incremental algorithm that maintains strong reconstruction guarantees for KRR problems in a sequential setting by incrementally computing estimates of ridge leverage scores.

The gist

The INK-Estimate algorithm processes a dataset in a single pass, maintaining a Nyström approximation of the kernel matrix based on RLS estimates, and provides strong approximation guarantees on the distance between the true kernel matrix and its approximation at any intermediate step.

Background and Problem Context

Kernel ridge regression (KRR) is commonly used but suffers from an O(n2) space requirement for storing the kernel matrix, making it intractable for large datasets. Nyström methods address this by subsampling columns of the kernel matrix to construct a low-rank approximation, reducing space complexity to O(nm). While sampling uniformly is simple, distributions based on ridge leverage scores (RLSs) provide strong reconstruction guarantees for Ke t. However, computing exact RLSs is computationally expensive. This paper addresses the need for sequential settings where guarantees must hold at intermediate steps and introduces an algorithm to incrementally compute RLS estimates without requiring access to previously seen columns outside the current approximation.

The INK-Estimate Algorithm

The INK-Estimate algorithm is designed to be space-efficient, requiring only a small, fixed space budget, q proportional to the effective dimension of the problem. The algorithm maintains a Nyström approximation Ke t based on RLS estimates. At each step t, it uses only this approximation and the newly received sample to incrementally update the RLS estimate and compute Ke t+1.

The core operation involves:

1. Receiving a new column kt+1 and scalar kt+1 at each time step t.

2. Invoking an (α, β)-oracle to compute approximate leverage scores τei,t for columns in the dictionary I t union the new column kt+1, and approximate effective dimension deeff(γ)t.

3. Setting the sampling probability pei,t+1 = min(τei,t+1/deeff(γ)t+1, pei,t).

4. Executing a Shrink-Expand procedure to update the dictionary I t to I t+1 based on these probabilities.

5. Computing St+1 using the updated dictionary and weights pbi,t+1.

6. Computing Ke t+1 using St+1 and Equation 5, which defines the Nyström approximation of the kernel matrix at time t+1.

Incremental Oracle Components

To enable the INK-Estimate algorithm, an (α, β)-oracle is required to provide approximate leverage scores and effective dimension estimates.

((

) Definition 2: An (α, β)-oracle returns an α-approximate ridge leverage scores τei,t satisfying 1/α τi,t(γ) ≤ τei,t ≤ τi,t(γ), and a β-approximate effective dimension deeff(γ)t satisfying deeff(γ)t ≤ βdeeff(γ)t.

(Lemma 2): For columns in the dictionary I t union the new column kt+1, the approximate RLS is bounded by: 1/α τi,t(γ) ≤ τei,t+1 ≤ τi,t(γ). This allows for an approximation of RLSs using only stored columns and the new sample. The paper notes that this approach preserves exact information of the matrix by using actual columns ki,t to compute the RLS instead of relying solely on Ke t approximations.

Guarantees and Complexity Analysis

The INK-Estimate algorithm provides strong approximation guarantees that hold at any intermediate step t.

(Theorem 2): The algorithm satisfies condition (11), which ensures that for all t, the Nyström approximation Ke t satisfies 0 ≤ Kt − Ke t ≤ γ/(1 − ε) Kt(Kt + γI)−1 ≤ γ/(1 − ε) I.

(Time Complexity): The time complexity is bounded as O α2β2n2deff(γ)2n + α3β3ndeff(γ)3n, which simplifies to O α4 (1 + ρ)2n2deff(γ)2 + O α6 (1 + ρ)3ndeff(γ)3, where ρ = λmax(Kt)/γ.

(Space Complexity): The space complexity is bounded as O nq), where q is the space budget, and it is shown that with high probability, the number of columns kept Qt is not much larger than q.

Key Findings on Incremental Updates

The paper addresses three main challenges in the sequential setting:

Here are the specific improvements that can be made to AI systems, based on the INK-Estimate algorithm described in this paper:

The core improvement lies in enabling large-scale Kernel Ridge Regression (KRR) and sequential online learning models to operate efficiently and maintain strong generalization guarantees without prohibitive memory or computational costs.

Here are the specific improvements:

1. Real-time/Online KRR with Strong Generalization Guarantees:

The system can perform Kernel Ridge Regression on a growing dataset sequentially (online setting) while maintaining an approximate solution that is guaranteed to be close to the optimal batch solution, even at intermediate steps.

2. Memory Efficiency for Large Datasets:

The system can handle massive datasets where storing the full kernel matrix is infeasible. Instead of storing an entire dense matrix, it only needs to store a small sketch (a dictionary) whose size scales with the effective dimension of the problem, which is often much smaller than the total number of samples.

3. Adaptive Sampling Distribution based on Leverage Scores:

Instead of using simple uniform random sampling (which performs poorly on coherent data), the system dynamically updates its sampling strategy at every step based on estimated Ridge Leverage Scores (RLSs). This ensures that samples most influential to the current regression task are prioritized for inclusion in the low-rank approximation.

4. Incremental and Robust Updates:

The algorithm is designed to be sequential; it processes data one sample at a time without requiring a full pass over the entire dataset at every step. It uses an incremental update mechanism (Shrink-Expand) to dynamically adjust which past samples are kept or discarded based on how much their influence (RLS) has decayed relative to the evolving effective dimension of the problem.

5. Guaranteed Performance at Any Time:

The system provides strong, quantifiable guarantees—specifically, a risk bound proportional to the exact batch solution's risk—not just at the end of training, but at every intermediate step. This allows for real-time decision-making or interruption of the process with a guaranteed high-quality model.

6. Improved Sample Selection Criterion:

The system introduces a novel criterion for sample inclusion: the Ridge Leverage Score (RLS). This criterion provides a more informed, adaptive mechanism than standard correlation or surprise criteria for deciding whether to include a new data point in the working dictionary, leading to better space-to-accuracy trade-offs.

The improved AI system can perform the following tasks:

1. Real-Time Predictive Modeling: Build and update a KRR model continuously as new data arrives (e.g., in streaming sensor data or online personalization systems) with confidence that the current model is a high-quality approximation of the true underlying function, without needing to re-train from scratch frequently.

2. Efficient Feature Space Reduction: Effectively reduce the dimensionality of complex feature spaces by only retaining a small, critical subset of previously seen samples (the dictionary), leading to faster inference times and lower memory footprints for high-dimensional kernel methods.

3. Robust Online Learning: Deploy KRR models in environments where data is arriving non-i.i.d., ensuring that the model's performance does not degrade significantly as the dataset grows, due to its ability to adapt its sampling based on evolving data structure (RLSs).

4. Guaranteed Model Quality Assurance: Provide a formal safety net for the model, allowing engineers to stop the learning process at any point and retrieve a solution with a mathematically proven error bound relative to the optimal solution.