Conditional Distribution Compression via the Kernel Conditional Mean Embedding

Existing distribution compression methods, like Kernel Herding (KH), were originally developed for unlabelled data. However, no existing approach directly compresses the conditional distribution of labelled data. To address this gap, we first introduce the Average Maximum Conditional Mean Discrepancy (AMCMD), a metric for comparing conditional distributions, and derive a closed form estimator. Next, we make a key observation: in the context of distribution compression, the cost of constructing a compressed set targeting the AMCMD can be reduced from O(n 3 ) to O(n). Leveraging this, we extend KH to propose Average Conditional Kernel Herding (ACKH), a linear-time greedy algorithm for constructing compressed sets that target the AMCMD. To better understand the advantages of directly compressing the conditional distribution rather than doing so via the joint distribution, we introduce Joint Kernel Herding (JKH), an adaptation of KH designed to compress the joint distribution of labelled data. While herding methods provide a simple and interpretable selection process, they rely on a greedy heuristic. To explore alternative optimisation strategies, we also propose Joint Kernel Inducing Points (JKIP) and Average Conditional Kernel Inducing Points (ACKIP), which jointly optimise the compressed set while maintaining linear complexity. Experiments show that directly preserving conditional distributions with ACKIP outperforms both joint distribution compression and the greedy selection used in ACKH. Moreover, we see that JKIP consistently outperforms JKH.

• In Section 4.1, we define the Average Maximum Conditional Mean Discrepancy (AMCMD), show that it satisfies the properties of a proper metric on the space of conditional distributions, and derive a closed form estimate. • In Section 4.2, we make a crucial observation: the cost of estimating the AMCMD, excluding terms irrelevant for distribution compression, can be reduced from O(n 3 ) to O(n) via application of the tower property.

• This observation enables the development of Average Conditional Kernel Herding (ACKH), a linear-time algorithm which constructs a compressed set such that PY |X=x ≈ P Y |X=x a.e. x wrt P X . Furthermore, in Section 4.3, we propose Average Conditional Kernel Inducing Points (ACKIP) as a non-greedy, linear-time alternative that jointly optimises the compressed set to the same end.

• For comparison purposes, in Section 3, we propose Joint Kernel Herding (JKH) and Joint Kernel Inducing Points (JKIP), extending existing compression algorithms to target the joint distribution.

• In Section 5, across various datasets and evaluation metrics, we show that directly targeting the conditional distribution via ACKIP is preferable to compressing the joint distribution via JKH or JKIP. We also demonstrate the limitations of the greedy heuristic used by JKH and ACKH, with JKIP and ACKIP outperforming their counterparts.