RD-DPP: Rate-Distortion Theory Meets Determinantal Point Process to Diversify Learning Data Samples

Xiwen Chen, Huayu Li, Peijie Qiu, Wenhui Zhu, Rahul Amin, Abolfazl Razi

Introduction: The "Small Pipe" Problem

In the era of "Big Data," we often face what researchers call "Small Pipe" problems. Whether it is an autonomous drone with limited battery or a remote sensor with low bandwidth, we cannot always process or transmit every data point. The challenge lies in selecting a representative subset of data that maximizes learning efficiency under strict resource constraints.

Traditional strategies typically fall into two camps: Diversity-based methods (like vanilla Determinantal Point Processes), which pick geometrically spread-out samples but are often task-agnostic, and Uncertainty-based methods, which pick samples near decision boundaries but fail in early learning stages or when the task shifts. This paper introduces RD-DPP, a method that bridges Information Theory and Geometry to create a task-oriented, robust data selection policy.

Methodology: Bridging Information Theory and Geometry

RD-DPP (Rate-Distortion Determinantal Point Process) rests on three primary pillars:

  1. The Theoretical Bridge: The authors prove that the "coding rate" from Rate-Distortion (RD) theory—the number of bits needed to represent a dataset—is mathematically related to the sum of subset probabilities in a DPP. Essentially, a more diverse dataset is harder to compress, providing a formal link between information content and geometric diversity.
  2. Semantic Diversity Kernel: Instead of relying on raw geometry, RD-DPP defines "semantic diversity." This measures how well a subset maintains within-class diversity while maximizing between-class discrimination, resulting in a custom kernel specifically tuned for classification tasks.
  3. Bi-Modal Scheduling: The algorithm uses a "house-building" analogy. It starts with RD-DPP to build the "framework" (diversity). Once diversity gain saturates at a specific threshold ($\phi_0$), it automatically switches to uncertainty-based selection for "interior finishing" (fine-tuning the decision boundary).

Key Results: Superior Performance at Low Budgets

RD-DPP consistently outperforms baselines such as Random selection, vanilla DPP, and K-Center across diverse datasets including MNIST, CIFAR-10, and SVHN. The method is particularly dominant at low budgets, which is the most critical scenario for real-world edge computing.

Accuracy vs. Budget for RD-DPP and baselines across different network architectures.

As shown in the performance curves, the gains are architecture-agnostic, holding steady across EfficientNet-B0, ResNet-18, and ResNeXt29. On MNIST, RD-DPP showed a 3%–5% gain, while on SVHN, it achieved a massive 7% lead over the next best method at low budgets.

Robustness and Task Generalization

A significant advantage of RD-DPP is its ability to handle "Task Shifts." Uncertainty-based methods tend to overfit to specific decision boundaries. Because RD-DPP captures the underlying geometry of the classes, the samples it selects remain useful even if the task changes (e.g., shifting from identifying "Smiling" faces to "Blond Hair").

Comparison of selection strategies under task shift.

In label-shift experiments on the CelebA dataset, RD-DPP maintained high F1 scores for new tasks, while uncertainty-based methods saw their performance plummet because they had only selected samples relevant to the original, now-obsolete decision boundary.

Conclusion and Future Work

RD-DPP offers a powerful framework for task-oriented data selection by proving that compressibility and diversity are two sides of the same coin. While the current theoretical link assumes Gaussian data distributions and involves some computational complexity due to SVD decompositions, its empirical success across seven diverse benchmarks makes it a compelling choice for resource-constrained machine learning. Future work may focus on generalizing the theoretical derivation for non-Gaussian data and further optimizing the computational overhead.

Summary updated

Abstract

Selecting representative samples plays an indispensable role in many machine learning and computer vision applications under limited resources (e.g., limited communication bandwidth and computational power). Determinantal Point Process (DPP) is a widely used method for selecting the most diverse representative samples that can summarize a dataset. However, its adaptability to different tasks remains an open challenge, as it is challenging for DPP to perform task-specific tuning. In contrast, Rate-Distortion (RD) theory provides a way to measure task-specific diversity. However, optimizing RD for a data selection problem remains challenging because the quantity that needs to be optimized is the index set of the selected samples. To tackle these challenges, we first draw an inherent relationship between DPP and RD theory. Our theoretical derivation paves the way to take advantage of both RD and DPP for a task-specific data selection. To this end, we propose a novel method for task-specific data selection for multi-level classification tasks, named RD-DPP. Empirical studies on seven different datasets using five benchmark models demonstrate the effectiveness of the proposed RD-DPP method. Our method also outperforms recent strong competing methods, while exhibiting high generalizability to a variety of learning tasks. The source code is available on https://github.com/xiwencl/RD-DPP1.
BibTeX
@inproceedings{chen2025rd,
  author = {Xiwen Chen and Huayu Li and Peijie Qiu and Wenhui Zhu and Rahul Amin and Abolfazl Razi},
  title = {{RD-DPP: Rate-Distortion Theory Meets Determinantal Point Process to Diversify Learning Data Samples}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2025},
  doi = {10.1109/wacv61041.2025.00672},
}
Figure