Research map / Learning theory and algorithms / Kernels and regression theory
Conditional Distribution Compression via the Kernel Conditional Mean Embedding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes AMCMD, a metric on families of conditional distributions, and linear-time compression algorithms (ACKH, ACKIP) plus joint-distribution counterparts (JKH, JKIP) for compressing labelled data's conditional distribution.
Problem
No existing distribution compression method targets the conditional distribution P(Y|X) of labelled data; computing kernel conditional mean embeddings costs O(n^3).
Approach
Define AMCMD as a proper metric between conditional distributions averaged over a conditioning distribution, show via the tower property that its compression-relevant cost drops from O(n^3) to O(n), and use greedy (ACKH) or joint gradient-based (ACKIP) optimisation of a compressed labelled set.
Key results
- ACKIP achieves the lowest RMSE across each test function on Superconductivity, with ACKH second for all but one.
- On the Imbalanced four-class dataset, the KCME trained on an ACKIP compressed set of size 250 (about 3% of data) closely matches full-data class-conditional probability accuracy.
- JKIP consistently outperforms JKH across the experimental settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ACKH or ACKIP to compress the conditional distribution instead of using JKH or JKIP to compress the joint distribution | Conditional distribution compression · True conditional distribution | AMCMD² | Helped |
| Jointly optimise the compressed set with ACKIP instead of greedily selecting pairs with ACKH | Conditional distribution compression · True conditional distribution | AMCMD² | Helped |
| Use ACKIP instead of JKH or JKIP | Conditional distribution compression · Superconductivity | RMSE | Helped |
| Use ACKIP instead of other compression methods | Conditional distribution compression · Heteroscedastic | RMSE | Mixed |
| Use ACKH instead of random sampling | Conditional distribution compression · Imbalanced | RMSE | Hurt |
| Jointly optimise the compressed set with JKIP instead of greedily selecting pairs with JKH | Joint distribution compression · Experiments across datasets | RMSE | Helped |
| Use JKIP instead of JKH | Joint distribution compression · Imbalanced | RMSE | Mixed |
| Use ACKIP to construct a compressed set for estimating class-conditional probabilities | KCME · Imbalanced | RMSE | Helped |
Surprising findings
- ACKH performs worse than random sampling on three of the four classes in the Imbalanced experiment, exposing limits of the greedy herding heuristic.
Limitations
- No formal convergence guarantee for the proposed algorithms.
- Gradient-based optimisation may be unsuitable for data where gradients are ill-defined, such as graphs or text.
- Compressed sets concentrate on high-density regions of P_X, giving less uniform coverage of the conditioning space.
Experimental setup
Datasets: Superconductivity (UCI) MNIST Synthetic Gaussian conditional (true distribution) Heteroscedastic synthetic Imbalanced synthetic four-class
Benchmarks: Superconductivity MNIST Heteroscedastic synthetic Imbalanced synthetic
Metrics: AMCMD^2 RMSE of conditional expectations across test functions
Baselines: Joint Kernel Herding Joint Kernel Inducing Points Average Conditional Kernel Herding random sampling
Builds on: Kernel Herding Gradient Flow Maximum Conditional Mean Discrepancy Joint Maximum Mean Discrepancy Kernel Thinning
Closest papers by meaning
- Debiased Distribution Compression (ICML 2024 · similarity 0.89)
- Kernel conditional tests from learning-theoretic bounds (NeurIPS 2025 · similarity 0.87)
- Supervised Kernel Thinning (NeurIPS 2024 · similarity 0.86)
- Kernel Quantile Embeddings and Associated Probability Metrics (ICML 2025 · similarity 0.86)
- Neural-Kernel Conditional Mean Embeddings (ICML 2024 · similarity 0.85)
- Learning to Embed Distributions via Maximum Kernel Entropy (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.