Abstract
We focus on the distribution regression problem: regressing to a real-valued response from a probability distribution. Although there exist a large number of similarity measures between distributions, the theoretical understanding of this task has remained limited. This paper provides the first rigorous theoretical guarantee for distribution regression using a simple two-stage kernel ridge regression approach, solving a 15-year-old open question regarding the validity of "set kernels."
Introduction
In standard machine learning, the objective is typically to map a vector input to a label. However, many modern applications involve inputs that are themselves probability distributions. This occurs frequently in "Multiple Instance Learning" (e.g., representing a patient by a collection of test results) or in statistical estimation tasks like entropy prediction.
The primary challenge in this domain is the two-stage sampling problem:
- We observe a finite number of distributions ($l$).
- For each distribution, we only observe a finite number of samples ($N_i$).
Previous approaches often relied on restrictive parametric assumptions or slow-converging methods like Kernel Density Estimation (KDE). This work establishes a more general, non-parametric framework that works directly on samples without density estimation.
Methodology: Mean Embeddings and Meta-Kernels
The authors propose a two-stage algorithm that leverages the power of Reproducing Kernel Hilbert Spaces (RKHS):
- Mean Embedding: Each "bag" of samples is mapped into an RKHS using a kernel $k$. This represents the distribution as a single point (a mean embedding) in a high-dimensional feature space.
- Kernel Ridge Regression: Standard ridge regression is then performed on these embeddings using a second "meta-kernel" $K$.
As shown in the table above, the theory accommodates various kernel types, including Gaussian ($K_G$), Exponential ($K_e$), Cauchy ($K_C$), and others, each characterized by a specific parameter $h$ that influences the convergence analysis.
Theoretical Results and Convergence
The core contribution of this paper is the mathematical analysis of the excess risk. By decomposing the error into five distinct terms, the authors separate the error stemming from the finite number of distributions from the error caused by finite samples per distribution.
The $P(b, c)$ Prior Class
To derive explicit rates, the authors define a general class of problems characterized by two parameters:
- $b$: The "effective dimension," representing how fast the eigenvalues of the covariance operator decay.
- $c$: The "smoothness" of the regression function.
As detailed in the table above, the authors establish that the method is statistically consistent under mild conditions. They provide explicit convergence rates; for instance, if the regression function is "smooth" ($c=2$) and the total number of samples $t = lN$ is fixed, they achieve a convergence rate of $O(t^{-2/7})$. This demonstrates that by using mean embeddings, the method effectively avoids the curse of dimensionality typically associated with high-dimensional density estimation.
Key Insights
- Validation of Set Kernels: For 15 years, "set kernels" (averaging pairwise similarities) were used heuristically. This paper proves they are mathematically sound and consistent for distribution regression.
- Generality: The theory is not restricted to Euclidean space; it applies to any domain where a valid kernel can be defined, including strings and graphs.
Applications and Future Work
The framework was evaluated on tasks such as Supervised Entropy Learning and Aerosol Prediction (using satellite imagery). While the current theory assumes bounded kernels and real-valued labels, future research may extend these guarantees to unbounded settings or more complex output spaces, such as regressing to another distribution. Additionally, determining whether these derived rates are "minimax optimal" remains an open question.
Summary updated