Abstract
Coreset is usually a small weighted subset of $n$ input points in $\mathbb{R}^d$, that provably approximates their loss function for a given set of queries (models, classifiers, etc.). Coresets become increasingly common in machine learning since existing heuristics or inefficient algorithms may be improved by running them possibly many times on the small coreset that can be maintained for streaming distributed data. Coresets can be obtained by sensitivity (importance) sampling, where its size is proportional to the total sum of sensitivities. Unfortunately, computing the sensitivity of each point is problem dependent and may be harder to compute than the original optimization problem at hand. We suggest a generic framework for computing sensitivities (and thus coresets) for wide family of loss functions which we call near-convex functions. This is by suggesting the $f$-SVD factorization that generalizes the SVD factorization of matrices to functions. Example applications include coresets that are either new or significantly improves previous results, such as SVM, Logistic regression, M-estimators, and $\ell_z$-regression. Experimental results and open source are also provided.
Introduction
In the era of "Big Data," the primary bottleneck for machine learning is often the time and memory required to process millions of data points. Researchers from the University of Haifa have proposed a powerful new way to shrink these massive datasets into tiny, representative "coresets" that work for a wide variety of common machine learning problems. A coreset is a small, weighted subset of the original data that acts as a high-fidelity proxy, yielding nearly the same loss function value as the full dataset for any possible model.
The gold standard for building coresets is sensitivity sampling, where points are sampled based on their "importance" to the total loss. However, calculating these sensitivities is typically as difficult as solving the original optimization problem, leading researchers to traditionally invent bespoke coreset algorithms for every specific problem. This work introduces a unified framework applicable to an entire family of functions, significantly streamlining the data summarization process.
Methodology: The f-SVD Framework
The authors identify a broad family of functions termed near-convex functions. These functions can be bounded from above and below by a combination of a convex function and a "well-behaved" error term. To handle this family, they introduce the f-SVD factorization, generalizing the standard Singular Value Decomposition (SVD) of matrices to functions.
The construction process follows three main steps:
- Geometric Bounding: The framework utilizes the Löwner ellipsoid—the smallest ellipsoid that contains the level set of the convex part of the function.
- Sensitivity Bounding: By mapping data points into the space defined by this ellipsoid, the sensitivity of every point in the dataset can be bounded simultaneously.
- Importance Sampling: Standard importance sampling is then applied to select the coreset based on these bounds.
This approach effectively decouples the "importance" of a data point from the specific model being trained, allowing for a "one-size-fits-many" solution.
Experimental Evaluation
The algorithm was evaluated on several real-world datasets from the UCI Machine Learning Repository, including:
- HTRU: Pulsar star detection (17,898 records).
- Skin: Face image samples (245,057 records).
- Cod-rna: RNA descriptions (59,535 records).
- Web: Web page records (49,749 records).
- 3D spatial networks: Road network elevation data (434,874 records).
Key Results and Insights
The f-SVD framework provides several significant breakthroughs:
- Breaking the $z \ge 1$ Barrier: Most existing coreset techniques for regression require convex losses (like $\ell_1$ or $\ell_2$). This paper provides the first coreset for $\ell_z$-regression where $0 < z < 1$, which is essential for robust statistics but notoriously difficult to optimize.
- Independence from $n$: For many problems, the size of the coreset depends on the dimensionality ($d$) and desired error ($\epsilon$), but is nearly independent of the number of original points ($n$). This allows for compressing billions of points into a few thousand without significant accuracy loss.
- Superior Accuracy: Experiments across SVM, Logistic Regression, and $\ell_z$-regression show that f-SVD coresets consistently outperform uniform sampling, providing much lower approximation error for the same data budget.
- Efficiency: The construction time is generally $O(nd^2)$, making it highly practical for large-scale data preprocessing.
Conclusion and Future Work
The f-SVD framework represents a major step toward a general theory of coresets, offering a unified mathematical lens for diverse problems. While currently limited by symmetry requirements in fitting the Löwner ellipsoid, future research aims to generalize the framework to broader classes, such as loglog-Lipschitz functions, and integrate advanced sketching techniques like Lewis weights to further optimize coreset sizes.
Summary updated