Many of the most powerful algorithms in machine learning suffer from a "quadratic wall." Whether it is Affinity Propagation for clustering or kernel-based methods, the computational cost often scales with the square of the number of data points ($O(n^2)$). When $n$ moves from thousands to millions, these algorithms become unusable.
To break this wall, a shared strategy has emerged across diverse fields: Recursive Reduction. Instead of processing a massive dataset all at once, researchers are using hierarchical "divide-and-conquer" frameworks to distill data into coresets—tiny, representative subsets that preserve the mathematical properties of the original whole.
The Geometry of the Shortcut
The intuition behind recursive reduction is simple: a global problem can often be approximated by the union of local solutions. If you want to cluster a billion points, you don't need to compare every point to every other point.
As Cyril Furtlehner and Xiangliang Zhang demonstrate in Scaling Analysis of Affinity Propagation, you can partition the data into small subsets, find local "exemplars" (representative points) for each, and then treat those exemplars as a new, smaller dataset to be clustered again. This recursive process transforms quadratic complexity into nearly linear complexity ($O(n \log n)$ or even $O(n)$).
This isn't just a heuristic for clustering. In the context of speech processing, Shih-Sian Cheng and colleagues showed in Speaker diarization using divide-and-conquer that recursive partitioning allows hierarchical methods to handle hours of audio by circumventing the bottleneck of global distance matrices.
Iterative Halving and Discrepancy
A central challenge in this direction is error accumulation. If you summarize a summary, don't you lose the original signal?
The solution lies in "Iterative Halving." In Discrepancy, Coresets, and Sketches in Machine Learning, Zohar S. Karnin and Edo Liberty use discrepancy theory to prove that you can repeatedly discard half of a dataset while keeping the approximation error extremely low. By carefully choosing which points to keep (often using "sketches"), the final coreset remains a faithful proxy for the original distribution.
This "cascading" reduction is taken to its logical extreme by Vladimir Braverman and Shaofeng H.-C. Jiang. In Coresets for Clustering in Excluded-minor Graphs and Beyond, they show how to compress a dataset from size $n$ to $\log n$, and then from $\log n$ down to a constant size that is completely independent of the original input size.
Sparsification through Importance Sampling
In numerical linear algebra, the recursive approach manifests as iterative sparsification. When dealing with massive matrices, David P. Woodruff and Taisuke Yasuda utilize "root ridge leverage scores" to sample the most important rows of a matrix.
As detailed in Nearly Linear Sparsification of ℓp Subspace Approximation, applying this sampling process recursively allows them to shrink a matrix until its size depends only on its rank, not the number of rows. This makes it possible to solve Least-Mean-Squares (LMS) problems and subspace approximations in streaming environments where you cannot store the full data. Alaa Maalouf and Dan Feldman further refine this in Fast and Accurate Least-Mean-Squares Solvers, using a hierarchical tree of sketches to maintain numerical stability that traditional fast solvers often sacrifice.
A Unified Meta-Algorithm
The research direction across these papers suggests a unified meta-algorithm for "Big Data" problems:
- Partition: Break the data into manageable chunks.
- Thin/Sketch: Use a primitive (like importance sampling or kernel thinning) to reduce each chunk.
- Merge: Combine the reduced chunks.
- Recurse: Repeat the process until the data fits in memory or reaches a target size.
This framework, formalized by Abhishek Shetty and Lester Mackey in Distribution Compression in Near-linear Time, provides a blueprint for scaling complex algorithms. By treating the "reduction primitive" as a black box, we can apply the same recursive logic to everything from Bayesian inference to Kernel Clustering, effectively turning $O(n^2)$ problems into $O(n)$ solutions.