PaperlayerView exact revision on arXiv

Source-linked AI summary

Conditional mean embeddings as regressors - supplementary

Steffen Grünewälder, Guy Lever, Luca Baldassarre, Sam Patterson, Arthur Gretton, Massimilano Pontil

arXiv:1205.4656v2cs.LGstat.ML

TL;DR

Conditional mean embeddings lacked a loss-based characterization that would connect them cleanly to standard regression tools. The paper establishes an equivalence with vector-valued regression, derives sparse estimators and near-optimal convergence rates, and evaluates sparsity in reinforcement learning.

  • Problem

    Conditional mean embeddings lacked an optimizer-based loss formulation despite existing consistency results, limiting extensions and parameter-selection methods.

  • Method

    The paper recasts conditional mean embeddings as vector-valued regressors using a natural regularized loss and an operator-valued kernel construction.

  • Results

    O(log(n)/n) convergence rates improve on O(n^-1/4), hold under milder assumptions, and are optimal up to a log(n) factor.

  • Takeaways & Limitations

    The framework supports sparse embeddings, cross-validation for parameter selection, and repeated use in reinforcement-learning settings with large samples.

  • Takeaways & Limitations

    The convergence analysis restricts the distribution class and assumes Γ_x is Hilbert-Schmidt, while infinite-dimensional output spaces may cause rate degradation.

Abstract

from arXiv · show

We demonstrate an equivalence between reproducing kernel Hilbert space (RKHS) embeddings of conditional distributions and vector-valued regressors. This connection introduces a natural regularized loss function which the RKHS embeddings minimise, providing an intuitive understanding of the embeddings and a justification for their use. Furthermore, the equivalence allows the application of vector-valued regression methods and results to the problem of learning conditional distributions. Using this link we derive a sparse version of the embedding by considering alternative formulations. Further, by applying convergence results for vector-valued regression to the embedding problem we derive minimax convergence rates which are O(\log(n)/n) -- compared to current state of the art rates of O(n^{-1/4}) -- and are valid under milder and more intuitive assumptions. These minimax upper rates coincide with lower rates up to a logarithmic factor, showing that the embedding method achieves nearly optimal rates. We study our sparse embedding algorithm in a reinforcement learning task where the algorithm shows significant improvement in sparsity over an incomplete Cholesky decomposition.

1. Introduction/Motivation

Conditional mean embeddings represent conditional expectations in RKHSs and support direct computation from samples. The paper characterizes them as solutions to vector-valued regression, enabling improved theory and sparse estimation.

  • Motivation: Conditional mean embeddings represent conditional expectations as RKHS functions and can compute them directly from observed samples.They avoid intermediate density estimation and numerical integration.
  • Motivation: Existing convergence results establish consistency under smoothness conditions, but the embeddings lacked an optimizer-based loss characterization.This gap hindered extensions and standard parameter-selection techniques such as cross-validation.
  • Contribution: The paper shows that conditional mean embeddings solve a vector-valued regression problem with a natural regularized loss.This links RKHS embeddings to standard Tikhonov regularized least-squares methods in multiple dimensions.
  • Contribution: The vector-valued regression connection yields novel embedding characterizations, faster convergence rates, and a sparse embedding formulation.The paper applies vector-valued regression theory to both theoretical guarantees and practical estimation.

2. Background

The paper introduces RKHS and vector-valued regression foundations for learning conditional mean embeddings from sampled input-output pairs. Kernel regularization produces a finite-sample regression estimator while controlling overfitting under boundedness and continuity conditions.

  • Conditional mean embeddings: Conditional mean embeddings map each input x to an RKHS element representing the conditional expectation operator for P(Y|X=x).For h in the output RKHS, the conditional expectation is obtained as an inner product with the embedding.
  • Conditional mean embeddings: The estimator uses a second kernel on X, kernel-matrix weights, and a regularization parameter λ to recover embeddings from i.i.d. samples.The weights are formed from a regularized inverse of the kernel matrix.
  • Conditional mean embeddings: The estimator is identified with an underlying vector-valued regression problem, which the paper formalizes through vector-valued RKHS theory.This establishes the bridge between conditional mean embeddings and vector-valued regressors.
  • Vector-valued regression and RKHSs: Vector-valued regression learns functions from X to a Hilbert space V using square loss and RKHS regularization.Regularization with respect to the vector-valued RKHS norm is used to prevent overfitting.
  • Vector-valued regression and RKHSs: A vector-valued RKHS is defined through continuity of evaluation functionals, with operator-valued kernels providing its reproducing structure.The associated RKHS is generated by kernel sections and supports regression solutions represented by finite coefficient systems.
  • Vector-valued regression and RKHSs: Bounded kernel operators control pointwise function norms, while continuity assumptions ensure RKHS functions are continuous.The continuity result assumes X is Polish, V is separable, and x↦Γ(·,x) is continuous.

3. Estimating conditional expectations

The paper formulates conditional mean embedding estimation as regularized vector-valued regression, yielding the standard embedding estimator for a particular operator-valued kernel. This equivalence supports validation-based parameter selection and clarifies when surrogate and target risks agree.

  • 3.1. The equivalence between conditional mean embeddings and a vector-valued regressor: Conditional mean embedding learning is formalized as vector-valued regression with outputs L(y_i, ·).The empirical problem uses training pairs {(x_i, L(y_i, ·))} and a regularized loss.
  • 3.1. The equivalence between conditional mean embeddings and a vector-valued regressor: The risk used for estimation is a sample-based surrogate because conditional expectations are not directly observed.The surrogate is related to the target risk through bounds using Jensen’s and Cauchy–Schwarz’s inequalities.
  • 3.1. The equivalence between conditional mean embeddings and a vector-valued regressor: Choosing Γ(x, x′) = K(x, x′)Id makes the vector-valued regression solution coincide with the conditional mean embeddings of Song et al., after rescaling λ.The corresponding loss is the objective minimized by the estimated embeddings, although it need not always equal the more natural target risk.
  • 3.2. Some consequences of this equivalence: The regression formulation enables ordinary cross-validation over kernel and regularization parameters and supports improved performance analysis.Validation selects parameters using the error on held-out embedding targets.
  • 3.3. Relations between the error functionals E and Es: If a true embedding µ* exists in HΓ, it uniquely minimizes both target and surrogate risks almost surely.More generally, controlling surrogate error and the HΓ norm is needed for low target error, making regularization important even with infinitely many samples.

4. Better convergence rates for embeddings

The paper applies vector-valued regression theory to conditional mean embeddings, obtaining faster convergence rates under milder assumptions than prior embedding results. Its upper rates are nearly minimax optimal, while the guarantees depend on restrictions including finite-dimensional output spaces and representability assumptions.

  • Rates and comparison: O(log(n)/n) is obtained for the embedding estimator under the stated regression assumptions.The estimate follows a prescribed regularization schedule and convergence assumptions discussed in the section.
  • Rates and comparison: The upper rates are complemented by minimax lower rates, showing optimality up to a logarithmic factor.For b < ∞, the lower-rate result rules out algorithms achieving better rates than the stated minimax scale.
  • Rates and comparison: Under the conditional-expectation representability assumption, the regression and embedding minimizers are almost everywhere equivalent and the risk converges to zero.When that assumption fails, convergence remains to the minimizer of the surrogate loss and the distance to the minimal error can still be bounded.
  • Assumptions: The guarantees require restrictions such as finite-dimensional output RKHSs, spectral conditions on the kernel, and existence of a minimizer with bounded RKHS complexity.The paper notes that the finite-dimensional assumption may be weakenable, but doing so requires deeper analysis.
  • Assumptions: The conditional-expectation representability and Hilbert-Schmidt assumptions can be difficult to verify and may fail even for finite-dimensional RKHSs.A concrete counterexample shows that the representability assumption cannot hold under the specified finite-dimensional kernel construction.

5. Sparse embeddings

The paper develops a sparse approximation of conditional mean embeddings by recasting approximation as a Lasso-like regression problem, then evaluates it in reinforcement learning against incomplete Cholesky sparsification.

  • Sparse approximation: The sparse approximation minimizes RKHS distance to the sample mean embedding, with the special case Γ = KId yielding an explicit optimization problem.The formulation uses W = (K + nλI)^−1 and links the approximation objective to the embedding cost.
  • Sparse approximation: Increasing γ trades approximation error for sparsity, producing solutions in which many entries of M are zero.At γ = 0, M = W and the approximation error is zero; larger γ increases sparsity and error.
  • Optimization: FISTA solves the equivalent optimization problem with O(1/√ϵ) iterations and O(n^2) cost per iteration.The algorithm uses a soft-thresholding operator in its updates.
  • Alternative regularizers: Alternative block penalties can sparsify input points, outputs, or pairs of examples through row-, column-, or group-structured regularization.The ℓ1,1 penalty can be replaced by block ℓ1/ℓ2 variants with different sparsification effects.
  • Reinforcement-learning experiment: The sparse algorithm uses labels, unlike incomplete Cholesky decomposition, which sparsifies using only the input-space distribution.The comparison is made in a reinforcement-learning pendulum swing-up task where repeated embedding evaluations make sparse solutions useful.

6. Outlook

The paper concludes that its regression connection yields sparse embeddings and near-optimal convergence rates, while identifying kernel choice and infinite-dimensional output spaces as important open issues.

  • Conclusions: The framework combines a sparse embedding algorithm, cross-validation procedure, improved convergence rates, and matching lower rates up to a logarithmic factor.The authors conclude that the embedding estimator achieves near-optimal rates.
  • Open questions: Replacing K(x,y)Id with other kernels Γ may exploit knowledge about the data-generating process.The paper presents this as an open direction rather than an established result.
  • Scope and limitations: When V is infinite dimensional, Γx is not Hilbert-Schmidt for Γ(x,y) = K(x,y)Id, although the cited convergence results assume Hilbert-Schmidt operators.The paper notes that this may signal degraded rates for the standard embedding estimator.
  • Open questions: The sparsity approach could be extended with regularizers that remove rows and columns of W in parallel.The paper also notes that alternative sparse regression regularizers may perform well on suitable problems.

A. Similarity of minimisers

Under the existence of a function representing conditional expectations through inner products with the true embedding, the surrogate regression loss has the true embedding as its minimizer, uniquely almost surely.

  • Minimizer characterization: If µ* represents every conditional expectation as ⟨h,µ*(X)⟩V, then µ* minimizes the relevant regression objectives.The result applies under the stated integrability assumptions.
  • Uniqueness: The minimizer is PX-a.s. unique.A second minimizer must agree with µ* on a measurable set of input points having probability one.
  • Approximate minimizers: With approximation error η and an approximate surrogate minimizer within δ of the optimum, the theorem bounds embedding error using η, δ, and RKHS norms.The bound is derived by relating the target error to similarity in the surrogate cost.
  • Proof strategy: The proofs use Jensen’s inequality and Fubini’s theorem to connect conditional-expectation identities with the surrogate loss.These steps support the minimizer and approximation-error arguments.

B.1. Simple assumptions to make the convergence theorems hold.

The convergence theorems are made applicable under compact input and output spaces, finite-dimensional output RKHS, continuous kernels, and Borel measure-space assumptions.

  • Scope: The paper states that weaker assumptions may be possible and does not claim this set is maximally general.This qualifies the scope of the theorem conditions.
  • Assumptions: The assumptions require X to be a compact subset of R^n, Y to be compact, and V to be a finite-dimensional RKHS.The spaces are equipped with norm-induced topologies and their respective Borel algebras.
  • Assumptions: The operator-valued kernel Γ and output kernel L are assumed continuous, implying L(y,y) ≤ B < ∞ for all y ∈ Y.These conditions are presented as sufficient for the cited convergence theorems, not as the most general possible assumptions.

B.1.2. DATA GENERATING DISTRIBUTION

The data-generating setup places observations on product spaces and uses Borel-algebra assumptions to ensure conditional probabilities and measurability. Additional structural assumptions make the relevant vector-valued RKHS separable and kernel operators well behaved.

  • The data are generated from a probability measure on X × Y and transformed through y ↦ L(y, ·) into X × V.
  • Borel algebras on the product spaces ensure that the regular conditional probabilities P(B|x) and ˜P(˜B|x) exist.
  • X is assumed Polish, while V is a separable Hilbert space; finite-dimensional RKHS choices for V guarantee separability.
  • Finite dimensionality of V ensures that the evaluation operators are Hilbert-Schmidt and that Γ(x, x) has finite trace.
  • If Γ is continuous and X is Polish with finite-dimensional V, then HΓ is separable; in particular, this holds for X = R^n and continuous Γ.
  • Continuity of Γ makes the scalar kernel mappings measurable when the spaces carry their Borel algebras.

B.3. Assumptions for the “true” probability measure

The convergence analysis requires integrability, attainment of the population-risk infimum, and structural conditions linking the conditional embedding to covariance operators. These assumptions support the stated RKHS representation and the empirical convergence result inherited from prior work.

  • The assumptions require the relevant measure-theoretic quantities and vector-valued functions to be integrable under the data-generating distribution.
  • The population-risk infimum is attained exactly when an approximately minimizing sequence remains bounded in RKHS norm.
  • The bounded-sequence condition yields a weakly convergent subsequence whose limit lies in HΓ and attains the infimum.
  • Under these conditions, µ(x) = UY|Xφ(x), and the empirical operator provides an estimate of the conditional mean embedding.
  • The prior embedding result assumes conditional expectations lie in HK, CXX is injective, and the associated operators satisfy boundedness or stronger Hilbert-Schmidt smoothness conditions.
  • The cited prior result uses δn = n^-1/4 for its convergence analysis.

C. Proofs

The proofs review the earlier n^-1/4 convergence guarantee, expose an assumption that can fail for a simple kernel construction, and justify the sparse embedding objective through RKHS error control.

  • The earlier operator result instead gives a Hilbert-Schmidt convergence bound of order n^-1/8 under its stated assumptions.
  • Under bounded K(x, x), the prior estimator achieves an n^-1/4 bound for the conditional-expectation error with probability tending to one.
  • For X = [−1, 1] and K(x, y) = xy, no probability measure satisfies one of the earlier assumptions when a uniformly positive function exists in V.
  • The sparse-objective justification bounds conditional-expectation error by the RKHS distance between the candidate embedding and the true embedding.
  • A sparse approximation remains accurate whenever the original estimator is accurate, because the relevant errors are related by the triangle inequality.
  • In the considered case, Γ(x, x′) = K(x, x′)Id and the coefficient matrix M is encouraged to be sparse, including through the Lasso formulation.
Loading 1205.4656v2…