📊 statistics

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

The paper introduces SQUEAK, a new algorithm for kernel ridge regression that improves upon the INK-Estimate method by using unnormalized ridge leverage scores to achieve a simpler, more space-efficient Nystrom approximation that avoids dependencies on the largest eigenvalue.

Original authors: Daniele Calandriello, Alessandro Lazaric, Michal Valko

Published 2026-04-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Daniele Calandriello, Alessandro Lazaric, Michal Valko

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a librarian in a massive, ever-growing library. Every day, thousands of new books arrive. You want to create a "Master Index" (the Kernel Matrix) so that when someone asks a question, you can find the answer instantly.

The problem? This library is so huge that a complete index would be too heavy to carry, too expensive to print, and would take a lifetime to update every time a new book arrives.

This paper introduces a clever new system called SQUEAK to solve this problem. Here is the breakdown of how it works using everyday analogies.

1. The Problem: The "Heavy Index" Dilemma

In machine learning, "Kernel Ridge Regression" is like trying to understand the relationship between every single book in your library. To do this perfectly, you need to compare every book to every other book.

If you have $n$ books, you need $n \times n$ pieces of information. If you have a million books, that’s a trillion pieces of info! It’s mathematically "heavy"—it crashes computers and runs out of memory.

2. The Old Solutions: "Random Guessing" vs. "The Perfectionist"

To save space, scientists usually try to create a "Mini-Index" (called a Nyström approximation) by picking only a few important books to represent the whole collection.

The Random Sampler (Uniform Sampling): This is like picking books at random to represent the library. It’s fast, but if you happen to miss all the science books and only pick novels, your index is useless.
The Perfectionist (Exact RLS): This method tries to find the "VIP books"—the ones that contain the most unique information. However, to figure out which books are VIPs, the Perfectionist has to read every single book first. By the time they finish the index, the library has already changed! It’s too slow for a growing library.

3. The SQUEAK Solution: The "Smart Scout"

SQUEAK is like hiring a group of Smart Scouts who walk through the library as the books arrive. They don't wait for the library to be finished; they work "on-the-fly."

Here is the SQUEAK strategy:

The "VIP Score" (Ridge Leverage Scores): Every time a new book arrives, the Scouts look at it and ask: "Is this book telling us something new, or is it just a repeat of what we already know?" If it’s unique, it gets a high "VIP Score."
The "Shrink and Expand" Dance:
- Expand: If a new book is a VIP, the Scouts immediately add it to the Mini-Index.
- Shrink: If an old book in the index suddenly becomes "boring" (because ten new books arrived that say the exact same thing), the Scouts quietly remove it from the index to save space.
No Heavy Math Required: Unlike previous methods that tried to calculate the "average importance" of all books (which is hard), SQUEAK just looks at the relative importance. It’s like saying, "I don't need to know the average weight of all books in the world; I just need to know if this book is heavier than the last one."

4. Why is this a big deal? (The "So What?")

The researchers proved that SQUEAK is a "Goldilocks" algorithm:

It’s Light: It doesn't need to store the whole library, only a small, highly relevant "summary" (the dictionary).
It’s Fast: It updates itself instantly as new data arrives. It doesn't need to restart from scratch.
It’s Accurate: Even though it’s only looking at a tiny fraction of the books, its "Mini-Index" is almost as good as the "Master Index" created by the Perfectionist.

In short: SQUEAK allows computers to learn from massive, streaming amounts of data by intelligently deciding what to remember and what to forget, without ever getting overwhelmed by the sheer volume.

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

1. Problem Statement

Kernel Ridge Regression (KRR) is a powerful non-parametric method, but it suffers from severe scalability issues. For $n$ samples, the kernel matrix $K_n$ requires $O(n^2)$ space and $O(n^3)$ time to solve, making it unfeasible for large-scale datasets.

To mitigate this, Nyström approximations are used to construct a low-rank approximation of $K_n$ by selecting a subset of $m$ columns. The accuracy of this approximation depends heavily on the sampling distribution:

Uniform sampling is inefficient for datasets with high coherence (weakly correlated columns).
Ridge Leverage Score (RLS) sampling is theoretically optimal (requiring $m$ proportional to the "effective dimension" of the matrix), but computing exact RLS is as computationally expensive as solving the original KRR problem.
Previous incremental methods (like INK-ESTIMATE) attempted to solve this but introduced dependencies on the largest eigenvalue ( $\lambda_{max}$ ), which can lead to worst-case space complexities of $O(n^3)$ .

2. Methodology: The SQUEAK Algorithm

The authors propose SQUEAK, an incremental, adaptive algorithm designed to build a Nyström dictionary by processing data points one by one. The methodology relies on two primary innovations:

A. Improved RLS Estimation
Instead of computing exact RLS, SQUEAK uses an $\alpha$ -approximate estimator ( $\hat{\tau}_{t,i}$ ). This estimator allows the algorithm to approximate the importance of a column using only the current dictionary and the new incoming data point, avoiding the need to store or invert the full kernel matrix.

B. Sequential/Adaptive Sampling (Dict-Update & Shrink/Expand)
SQUEAK manages the dictionary $I_t$ dynamically through two processes:

SHRINK (Dict-Update): As new data arrives, the importance (RLS) of existing columns may decrease. SQUEAK uses a binomial sampling scheme to stochastically reduce the number of copies of a column in the dictionary. If a column's importance drops sufficiently, it is dropped entirely.
EXPAND: New incoming columns are added to the dictionary with a number of copies (up to a parameter $q$ ) proportional to their estimated RLS.

Crucially, SQUEAK does not normalize probabilities by the effective dimension ( $d_{eff}$ ), which simplifies the implementation and removes the dependency on $\lambda_{max}$ .

3. Key Contributions

Complexity Independence: Unlike previous incremental methods, SQUEAK’s space complexity does not depend on the largest eigenvalue ( $\lambda_{max}$ ) or the minimal eigenvalue ( $\lambda_{min}$ ), making it robust to various kernel spectra.
Single-Pass Capability: SQUEAK can operate in a single pass over the dataset, making it suitable for streaming data. It only needs to store the samples currently in the dictionary.
Adaptive Dictionary Size: The algorithm automatically scales the dictionary size to match the growth of the effective dimension of the data without requiring prior knowledge of that dimension.

4. Results and Theoretical Guarantees

The paper provides several rigorous guarantees (Theorem 1):

Approximation Accuracy: With high probability, the Nyström approximation $\hat{K}_n$ is a $\gamma$ -approximation of the true kernel $K_n$ .
Space Complexity: The number of stored columns is $O(d_{eff}(\gamma)_n \log(n/\delta))$ . This is only a constant factor worse than the "ideal" case where exact RLS is known in advance.
Risk Bound: The regression risk of the approximate solution $\hat{w}_n$ is bounded by a factor of roughly $(1 + \gamma/\mu)$ relative to the optimal solution $w_n$ .
Worst-Case Performance: Even in the worst-case scenario (where $d_{eff} = n$ ), the space complexity is only $O(n \log n)$ , which is significantly better than the $O(n^2)$ required for the full matrix.

5. Significance

SQUEAK represents a significant advancement in scalable kernel methods. By bridging the gap between the theoretical optimality of RLS sampling and the practical necessity of incremental, low-memory processing, it provides a robust tool for large-scale machine learning. Its design makes it applicable not only to KRR but also to related problems like Kernel PCA and distributed learning environments, where multiple machines can build and merge dictionaries in parallel.