Abstract
Faced with massive data, is it possible to trade off (statistical) risk, and (computational) space and time? This challenge lies at the heart of large-scale machine learning. Using k-means clustering and Gaussian Mixture Models (GMMs), this work demonstrates that "excess" data can be leveraged to reduce computation time through the use of coresets and a novel algorithm, TRAM.
Introduction
In classical machine learning, the relationship between data size ($n$) and statistical risk ($\epsilon$) is well-understood: more data generally improves accuracy. However, in large-scale engineering contexts, more data often implies increased running time ($t$) and memory usage ($s$). This paper challenges the view of large datasets as a purely computational burden. Instead, it explores how an abundance of data can be used as a resource to create efficient summaries, thereby reducing the time required to reach a target risk level.
The Tradeoff Framework
The authors categorize the interactions between space, time, data, and risk into specific tradeoffs. For instance, in a "Data-Time" tradeoff, the goal is to minimize the objective (time) while varying the data size and keeping risk fixed.
As illustrated in the trends table above, increasing the summary size ($s$) reduces summarization error ($\epsilon_{summarization}$), while increasing the total data size ($n$) reduces estimation error ($\epsilon_{estimation}$). The total risk is a combination of modeling, estimation, and summarization errors. The paper identifies an "intermediate regime" where increasing $n$ allows for the creation of better small summaries, which actually reduces the total computation time needed to hit a risk target.
Methodology: Coresets and TRAM
The proposed approach relies on two primary innovations:
- Coresets: Rather than simple uniform subsampling, the authors utilize coresets—small, weighted subsets of data that provide mathematical guarantees on approximating the full dataset's cost function. Coresets are particularly effective at capturing outliers that define cluster boundaries, which uniform sampling might miss.
- TRAM (TRadeoff nAvigation algorithM): To avoid the need for a manual "tuning oracle," TRAM iteratively increases the summary size and evaluates performance on a validation set, stopping once the target risk is achieved. This allows for practical navigation of the space-time-data-risk tradeoffs.
Empirical Results
The methodology was evaluated on diverse datasets, including synthetic Gaussian mixtures, protein homology data (KDD2004BIO), seismic data (CSN), and massive click logs (Yahoo! Webscope).
Key findings include:
- Non-trivial Tradeoffs: Experiments confirmed that for a fixed risk level, the optimal running time $t^*$ is non-increasing as data size $n$ increases.
- Coreset Superiority: Coresets consistently provided a more aggressive reduction in running time for the same level of risk compared to uniform sampling, as seen in the Data-Time and Risk-Time plots.
- Scalability: On the Yahoo! dataset with 45 million points, summarization reduced processing time from weeks to minutes while maintaining high likelihood on hold-out data.
Conclusion and Future Work
This research demonstrates that "data weakening" via coresets is a viable strategy for large-scale unsupervised learning. By strategically summarizing data, practitioners can navigate the complex tradeoffs between computational resources and statistical accuracy. While the current work focuses on $k$-means and GMMs, future research will aim to develop efficient coreset techniques for a broader range of supervised and unsupervised tasks.
Summary updated