Scalable and Adaptive Distribution Regression via Random Features

TL;DR

The paper introduces RaDR, a scalable method for distribution regression using random features that maintains theoretical guarantees while reducing computational cost. It further proposes A-RaDR, an adaptive version that dynamically allocates features based on learning performance, improving accuracy without sacrificing speed. Experiments confirm both methods deliver strong performance across diverse datasets.

Why It Matters

Distribution regression is crucial for tasks involving grouped or set-valued data, but traditional kernel methods are slow and sensitive to design choices. This work enables faster, more flexible learning by combining theoretical rigor with practical efficiency, making advanced distribution-level modeling accessible for real-world applications.

Key Findings

• RaDR achieves computational efficiency by using random features while preserving the excess-risk bounds of exact kernel-based distribution regression under two-stage sampling.
• A-RaDR adaptively allocates random features based on a score-guided strategy, leading to improved predictive accuracy compared to fixed allocation.
• Empirical results on synthetic and real-world datasets show both methods maintain competitive performance with significant speedups over baseline approaches.