Distribution regression—learning a mapping from probability distributions to response variables—underlies kernel methods, multi-instance learning, and set-valued learning. Standard kernel-based approaches are powerful but computationally heavy and depend strongly on the choice of kernel. In a new arXiv paper, Wang, Liu, and Ding propose random feature approximations to make this class of models both scalable and less kernel-sensitive.
Building on random features, the authors develop a finite-sample analysis of Random Feature Distribution Regression (RaDR) under two-stage sampling. Their perturbation analysis separates the effects of distribution-level sampling, within-bag sampling, and random feature approximation. They show that, given a sufficient feature budget, RaDR preserves the order of the excess-risk upper bound of exact two-stage kernel distribution regression while remaining computationally efficient.
The paper also introduces Adaptive Random Feature Distribution Regression (A-RaDR), which allocates random features according to downstream learning objectives. Experiments on synthetic benchmarks and 41 real-world datasets show that RaDR delivers substantial computational savings with competitive predictive performance, while A-RaDR further improves accuracy without sacrificing speed. Together, the results offer a theoretically grounded and practical framework for adaptive, scalable distribution learning.