Learning Theory for Distribution Regression

By Zoltán Szabó, Bharath K. Sriperumbudur, Barnab'as P'oczos, Arthur Gretton. 2014

155 citations recorded by the source corpus.

We focus on the distribution regression problem: regressing to vector-valued outputs from probability measures. Many important machine learning and statistical tasks fit into this framework, including multi-instance learning and point estimation problems without analytical solution (such as hyperparameter or entropy estimation). Despite the large number of available heuristics in the literature, the inherent two-stage sampled nature of the problem makes the theoretical analysis quite challenging, since in practice only samples from sampled distributions are observable, and the estimates have to rely on similarities computed between sets of points. To the best of our knowledge, the only existing technique with consistency guarantees for distribution regression requires kernel density estimation as an intermediate step (which often performs poorly in practice), and the domain of the distributions to be compact Euclidean. In this paper, we study a simple, analytically computable, ridge regression-based alternative to distribution regression, where we embed the distributions to a reproducing kernel Hilbert space, and learn the regressor from the embeddings to the outputs. Our main contribution is to prove that this scheme is consistent in the two-stage sampled setup under mild conditions (on separable topological domains enriched with kernels): we present an exact computational-statistical efficiency trade-off analysis showing that our estimator is able to match the one-stage sampled minimax optimal rate [Caponnetto and De Vito, 2007; Steinwart et al., 2009]. This result answers a 17-year-old open question, establishing the consistency of the classical set kernel [Haussler, 1999; Gaertner et. al, 2002] in regression. We also cover consistency for more recent kernels on distributions, including those due to [Christmann and Steinwart, 2010].

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, background): “2016), distribution regression (Szabó et al. 2016) and model selection in generative models (Bounliphone et al.”
Prototypal Analysis and Prototypal Regression (2017, background): “Szabó et al. (2015, 2016) performs a similar extension for kernel ridge regression.”
Kernel-Based Just-In-Time Learning for Passing Expectation Propagation Messages (2015, methodology): “The learning algorithm takes the form of a distribution regression problem, where the inputs are probability measures represented as embeddings of the distributions to a reproducing kernel Hilbert space (RKHS), and the outputs are vectors of message parameters (Szabó et al., 2014).”
Deep Sets (2017, background): “…however, can only deal with ﬁxed, ﬁnite-dimensional representations, and researchers only recently started to investigate the case when the inputs or outputs are permutation invariant sets rather than ﬁnite dimensional vectors (Oliva et al., 2013; Szabo et al., 2016; Muandet et al., 2013; 2012).”
Towards a Learning Theory of Cause-Effect Inference (2015, background): “Szabó et al. (2014) presented the first theoretical analysis of distributional learning based on kernel mean embedding (Smola et al., 2007), with focus on kernel ridge regression.”
Proposal : Scalable , Active and Flexible Learning on Distributions (2015, unknown): “Szabó et al. (2014) proved learning-theoretic bounds on the use of ridge regression with mmd.”
Learning from Conditional Distributions via Dual Embeddings (2016, background): “, stochastic average appproximation (SAA) and learning with kernel embedding [18], an advantage of the proposed method is that it requires only one sample from each conditional distribution.”
Two-stage sampled learning theory on distributions (2014, background): “[37] Zoltán Szabó, Bharath Sriperumbudur, Barnabás Póczos, and Arthur Gretton.”