Learning and Data Selection in Big Datasets

Hossein Shokri Ghadikolaei, Hadi G. Ghauch, Carlo Fischione, Mikael SkoglundICML 2019

In the era of "Big Data," we often assume that more is always better. However, training massive models on millions of samples is computationally expensive and often impossible in bandwidth-constrained environments like IoT sensors or edge devices. This paper asks a provocative question: How much of our data is actually redundant?

The Problem: Redundancy in Massive Datasets

Modern machine learning relies on increasingly massive datasets, but much of this data is redundant, carrying little to no additional information for the specific learning task.

While Active Learning tries to find the best samples to label, it is often greedy and doesn't scale well. Core-set selection tries to find representative subsets, but existing methods are often limited to specific algorithms like SVMs. The authors address the gap of finding a "small representative dataset" for generic learning tasks, particularly for applications like Edge Computing and Multi-Agent Systems, where sending a full dataset over a network is prohibited by power and bandwidth constraints.

Proposed Method: Joint Optimization for Data Selection

The authors formulate the problem as a joint optimization task: they want to find the best model parameters ($h$) and a binary selection vector ($z$) that picks $K$ samples out of $N$.

To solve this non-convex combinatorial problem, they use Block Coordinate Descent (BCD), alternating between two steps:

  1. The D-step (Data Selection): Given the current model, which $K$ samples should we keep? The authors prove that the optimal solution is surprisingly simple: calculate the loss for every sample, sort them, and keep the $K$ samples with the smallest losses.
  2. The F-step (Function Approximation): Given the selected subset, update the model parameters to minimize the empirical risk on those specific samples.

They demonstrate this approach using Extreme Learning Machines (ELM)—a type of neural network where only the last layer is optimized—which allows for efficient, convex optimization during the F-step.

Key Insights and Results

The paper evaluates the algorithm on a mix of synthetic "toy" functions and five real-world regression datasets (Bodyfat, Housing, Space-ga, YearPredictionMSD, and Power Consumption).

  • Sub-linear Growth: Theoretically, the size of the "sufficient dataset" ($K$) grows sub-linearly with the total size of the dataset ($N$). This means as your data grows, the percentage of it you actually need to keep shrinks.
  • The "Double Exponential" Tail: In smooth functions, the generalization error remains nearly flat as you compress the data, only spiking at very high compression ratios (e.g., after 90% or 95% of the data is removed).
Function approximation and generalization error
  • Joint Effects Matter: Unlike "influence functions" that look at the importance of samples in isolation, this joint optimization captures how samples work together to define the model's boundaries.
  • Simplicity of Selection: The finding that simply picking samples with the lowest current loss is the optimal "D-step" provides a very computationally efficient way to prune data ($O(N)$ complexity).
  • Massive Compression: On the largest dataset (YearPredictionMSD), the authors achieved 95% compression with almost no increase in generalization error compared to training on the full 100% of the data.
  • Outperforming Benchmarks: The proposed method consistently outperformed random sampling and influence-based selection, especially at high compression rates (75% to 95%).

Limitations and Future Directions

  • Stationary Points: Because the problem is non-convex, the BCD algorithm is only guaranteed to converge to a stationary point, not necessarily the global optimum.
  • The $\epsilon$ Parameter: The method relies on a user-defined error tolerance ($\epsilon$). Choosing the "right" $\epsilon$ requires some prior knowledge or a preliminary run on the full dataset.
  • Model Specificity: While the framework is generic, the experimental results focus heavily on regression and ELMs. The authors suggest that extending this to deep neural networks (which are multi-convex) is possible but would require more complex "block successive upper-bound minimization" techniques.

Summary updated

BibTeX
@inproceedings{ghadikolaei2019learning,
  author = {Hossein Shokri Ghadikolaei and Hadi G. Ghauch and Carlo Fischione and Mikael Skoglund},
  title = {{Learning and Data Selection in Big Datasets}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
}
Figure