Coresets for Near-Convex Functions

Murad Tukan, Alaa Maalouf, Dan Feldman

Introduction

In the era of big data, training machine learning models on massive datasets is computationally expensive. Coresets offer a powerful solution by selecting a tiny, weighted, representative subset of the data that preserves the "loss" of the original dataset within a provable error margin ($\epsilon$).

However, existing coreset methods suffer from two major drawbacks:

  1. Problem Specificity: Most coresets are "bespoke"—designed for one specific algorithm (e.g., exclusively for $k$-means or linear regression).
  2. Computational Complexity: Building a coreset usually requires calculating the "sensitivity" (importance) of every data point. Ironically, calculating these sensitivities is often as difficult, or even harder, than solving the original optimization problem.

This paper introduces a generic framework for constructing coresets for a broad family of "near-convex" loss functions. By generalizing Singular Value Decomposition (SVD) into a novel $f$-SVD factorization, the authors provide a unified method to bound data sensitivity, enabling faster and more efficient training for models like SVMs, Logistic Regression, and outlier-resistant regressions.

Methodology: The $f$-SVD Framework

The researchers bridge the gap between bespoke coresets and general applicability through two primary innovations:

  • Near-Convex Functions: They define a new family of loss functions that are "sandwiched" between a convex function ($g$) and a secondary function ($h$). This family is broad enough to include Support Vector Machines (SVM), Logistic Regression, and $\ell_z$-regression.
  • The $f$-SVD Factorization: This is a functional generalization of the standard SVD used in linear algebra. It uses the geometric properties of the Löwner ellipsoid (the smallest ellipsoid containing a convex set) to bound the total loss of the dataset.
Geometric intuition behind f-SVD factorization, showing a function bounded by simpler geometric shapes (ellipsoids) to estimate data importance.
  • Sensitivity Bounding: By using $f$-SVD, the authors can efficiently compute an upper bound on the sensitivity of each point without solving the full optimization problem. They then use importance sampling—picking points with a probability proportional to their sensitivity—to build the final coreset.

Key Insights

  • Geometric "Sandwiching": The core "aha!" moment is realizing that if you can bound a complex loss function between two simpler geometric shapes (ellipsoids), you can use the properties of those shapes to estimate the importance of data points.
  • Unified Theory: Instead of writing a new paper for every new loss function, researchers can now check if a function meets the "near-convex" criteria and apply this framework immediately.
  • Handling Outliers: The framework provides the first known coreset for $\ell_z$-regression where $z \in (0, 1)$, a common technique for making models resistant to outliers.
  • Size Independence: For many problems, the resulting coreset size is independent of the original number of points ($n$), meaning the summary doesn't have to grow just because the raw data does.

Experimental Results

The authors evaluated their framework on several real-world datasets from the UCI Machine Learning Repository, including HTRU (Pulsar stars), Skin (RGB face samples), Cod-rna, Web datasets, and 3D spatial networks.

  • Theoretical Efficiency: The authors provide new or improved coreset size bounds for Logistic Regression, SVM, and M-estimators.
  • Accuracy vs. Size: In experiments, their coreset consistently achieved much lower approximation error than uniform sampling for the same number of points.
  • Speedup: While some previous specialized SVM coreset methods existed, the authors' approach was significantly faster to compute while maintaining comparable or better accuracy.
Experimental results demonstrating that the proposed coreset achieves lower approximation error (left) and faster overall computation time (right) compared to uniform sampling and full data usage.
(Note: The authors have also provided an open-source implementation to allow other researchers to apply $f$-SVD to their own problems.)

Limitations and Future Directions

While highly versatile, the current definition of "near-convex" requires the level sets of the functions to be centrally symmetric. Removing this symmetry constraint is a key step for generalizing the framework further. Additionally, the authors suggest that future work could extend these techniques to even more complex classes, such as "loglog-Lipschitz" functions, and express interest in integrating state-of-the-art sampling techniques like "Lewis weights" into their generalized framework.

Summary updated

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.
BibTeX
@inproceedings{tukan2020coresets,
  author = {Murad Tukan and Alaa Maalouf and Dan Feldman},
  title = {{Coresets for Near-Convex Functions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=WhFpbKs3kSt},
}
Figure