Scalable and Adaptive Distribution Regression via Random Features

Yinsong Wang; Xiao Liu; Yu Ding

stat.MLOct 17, 2026

Scalable and Adaptive Distribution Regression via Random Features

Authors: Yinsong Wang, Xiao Liu, Yu Ding

Organizations: School of Mechanical, Industrial and Material Engineering, University of Nevada Reno, Reno 89557, USA. · H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta 30332, USA.

Abstract

Distribution regression seeks to learn mappings from probability distributions to response variables and has emerged as a unifying framework for kernel methods, multi-instance learning, and set-valued learning. Despite its success, kernel-based distribution regression remains computationally expensive and sensitive to kernel choice, motivating scalable and adaptive representations. Building on random feature approximations, we develop a finite-sample analysis of Random Feature Distribution Regression (RaDR) under two-stage sampling. Our perturbation analysis separates the effects of distribution-level sampling, finite within-bag sampling, and random feature approximation. We establish sufficient feature-budget conditions under which RaDR preserves the order of our excess-risk upper bound for exact two-stage kernel distribution regression while maintaining computational efficiency. We further propose Adaptive Random Feature Distribution Regression (A-RaDR), a unified score-guided framework that adaptively allocates random features according to downstream learning objectives. Experiments on synthetic benchmarks and 41 real-world datasets demonstrate that RaDR delivers substantial computational savings while maintaining competitive predictive performance, whereas A-RaDR further improves learning accuracy in distribution regression while retaining the computational speed up. Together, these results establish a practical and theoretically grounded framework for adaptive, scalable distribution learning

Figures & tables

Algorithm	KME	RF	Deep	Kernel	Reference
KME_Linear	✓			Linear	( Szabó et al., 2016 )
KME_Gaussian	✓			Gaussian	( Szabó et al., 2016 )
AKME_DV_Linear	✓			Linear	( Kachaiev and Recanatesi, 2024 )
AKME_DV_Gaussian	✓			Gaussian	( Kachaiev and Recanatesi, 2024 )
AKME_MDKE_Linear	✓			Linear	( Kachaiev and Recanatesi, 2024 )
AKME_MDKE_Gaussian	✓			Gaussian	( Kachaiev and Recanatesi, 2024 )

Table 1: Summary of benchmark algorithms used throughout the empirical study.

Figure 1: Accuracy and training time of RaDR and A-RaDR as the number of random features varies. The dashed horizontal line denotes exact KME-based distribution regression.

Figure 2: The feature pool multiplier ablation study. Left two columns : Classification accuracy differences between A-RaDR algorithms vs vanilla RaDR algorithm. Right two columns : Accuracy improvements divided by computational overhead (A-RaDR runtime/RaDR runtime). A-RaDR algorithms shows clear benefits in low random feature regime, but the difference diminishes as the random feature count increases.

Figure 3: Marginal sensitivity of predictive accuracy to training and testing bag sizes under fixed and variable bag-size settings. Increasing training bag size produces only limited improvements, whereas larger testing bags substantially improve predictive performance. RaDR closely follows the behavior of its exact KME counterparts across all bag-size regimes.

Figure 4: Training-time surfaces as functions of training and testing bag sizes. KME-based distribution regression exhibits strong dependence on training bag size, resulting in highly asymmetric computational scaling. In contrast, RaDR displays nearly symmetric scaling with respect to training and testing bag sizes due to its finite-dimensional random feature representation.

Name	Type	# Datasets	Dimension	Bag Size	# Bags
Musk	molecular activity	$1$	$166$	$2-40$	$92$
Mutagenesis	molecular activity	$2$	$7$	$26-88$	$42-188$
Protein	molecular activity	$1$	$8$	$35-189$	$193$
Animal	Image Annotation	$3$	$230$	$1-13$	$200$
Corel	Image Annotation	$20$	$9$	$2-13$	$2000$
UCSB Breast Cancer	Histopathology Analysis	$1$	$708$	$21-40$	$58$

Table 2: Dataset information summary for the 41 real-world benchmark datasets.

Algorithm	Accuracy	Training Time (s)
KME_Linear	$0.9347\pm 0.0016$	$264.37\pm 1.30$
KME_Gaussian	$\mathbf{0.9398\pm 0.0015}$	$255.16\pm 2.44$
AKME_DV_Linear	$0.9022\pm 0.0017$	$37.03\pm 0.26$
AKME_DV_Gaussian	$0.9110\pm 0.0016$	$36.77\pm 0.29$
AKME_MDKE_Linear	$0.9091\pm 0.0016$	$40.64\pm 0.26$
AKME_MDKE_Gaussian	$0.9226\pm 0.0016$	$42.29\pm 0.26$

Table 3: Average real-data benchmark performance over 41 complete MIL datasets. Reported values are mean

\pm

propagated standard error. The top 4 accuracy and the fastest training time are marked in bold .

Figure 5: The performance frontier (best accuracy) across the four algorithm groups. X-axis represents the relative training speed up over KME_Gaussian algorithm, computed as

\text{KME\_Gaussian Runtime}/\text{Algorithm Runtime}

. A-RaDR frontier strikes a balance between computation and performance, ranking second in both criteria.

Distributional Regression

See all 13 papers

Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees
Aug 26, 2026Caixing Wang, Zhibo Chen, Yue WangRandom Feature Methods Kernel Ridge Regression
School of Statistics and Data Science, Southeast University · Faculty of Business for Science and Technology, School of Management, University of Science and Technology of China
On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning
Oct 13, 2026Caixing WangRandom Feature Methods Kernel Ridge Regression
School of Statistics and Data Science, Southeast University, Nanjing, China
Sufficiently Reduced Distributional Regression
Sep 24, 2026Alexander Henzi, Tiange Liu, Xinwei ShenConditional Distribution Estimation Inverse Dimensionality Reduction
Tsinghua University, Department of Statistics and Data Science · University of Washington

Aug 26, 2026J/K move · Enter open · S save

Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees

Caixing Wang, Zhibo Chen, Yue Wang

School of Statistics and Data Science, Southeast University · Faculty of Business for Science and Technology, School of Management, University of Science and Technology of China

Random Feature Methods Kernel Ridge Regression Statistical Learning Theory Early Stopping

Open paper AskPDF arXiv

Random feature methods provide a scalable approximation to kernel ridge regression (KRR), but the regularization parameter that yields the oracle learning rate depends on unknown smoothness and capacity parameters. In this work, we propose a neighboring early-stopping rule for adaptive regularization in KRR with random features (KRR-RF). The method uses a grid that is uniform in inverse regularization and compares only adjacent estimators, reducing the number of discrepancy comparisons relative to standard all-pairs Lepskii-type procedures. Both the neighboring discrepancy and its empirical complexity term can be computed directly in the random feature space, without constructing the exact kernel Gram matrix. We establish a high-probability comparison bound for neighboring KRR-RF estimators and show that, under standard source and capacity conditions together with suitable grid and random feature budget conditions, the selected estimator attains the oracle polynomial learning rate up to logarithmic factors. The result allows the regularization parameter to be selected without prior knowledge of the source and capacity exponents and covers both well-specified and partially misspecified regimes. Our analysis is based on an empirical random feature effective dimension that connects the observable stopping threshold with the population complexity of the random feature model. Simulation and real-data experiments illustrate the prediction performance and computational behavior of the proposed method in comparison with standard tuning procedures.

Abstract

Distributional Regression

Explore similar work

Adaptive Regularization for Random Features: A Neighboring Early-Stopping Rule with Oracle-Rate Guarantees

On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning

Sufficiently Reduced Distributional Regression