Conditional Distribution Compression via the Kernel Conditional Mean Embedding
Authors: Dominic Broadbent
Nick Whiteley
Robert F Allison
Tom Lovett
Venue: NeurIPS 2025 poster ()
Keywords: compression
herding
distribution compression
conditional distribution
joint distribution
inducing points
kernel conditional mean embedding
kernel mean embedding
rkhs
reproducing kernel hilbert space
Primary area: general_machine_learning
TL;DR: We extend the concept of distribution compression to joint and conditional distributions, introducing algorithms to produce compressed sets that approximate the joint or conditional distribution of a target dataset.

Abstract: 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 $\mathcal{O}(n^3)$ to $\mathcal{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.

Conditional Distribution Compression via the Kernel Conditional Mean Embedding
Dominic Broadbent
Nick Whiteley School of Mathematics University of Bristol Bristol, United Kingdom
School of Mathematics University of Bristol
Bristol, United Kingdom
dominic. broadbent@bristol........oo. ac.uk uk
Robert Allison
Tom Lovett
School of Mathematics University of Bristol Bristol, United Kingdom
Mathematical Institute University of Oxford Oxford, United Kingdom
Abstract
Existing distribution compression methods, like Kernel Herding (KH), were orig- inally 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), metric for comparing conditional distributions, and derive closed form estima- tor. Next, we make key observation: in the context of distribution compression, the cost of constructing a compressed set targeting the AMCMD can be reduced from (n²) to On)). Leveraging this, we extend KH to propose Average Condi- tional Kernel Herding (ACKH), linear-time greedy algorithm for constructing compressed sets that target the AMCMD. To better understand the advantages 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 labelled data. While herding methods provide simple and interpretable selection process, they rely
greedy heuris- tic. 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 ACKH. Moreover, that JKIP consistently outperforms JKH.
Introduction
Given a large unlabelled dataset D = {a:31 C X' sampled i.i.d. from the distribution Px, major challenge constructing compressed set, C= { with m & n, that preserves the essential statistical properties of the original data. This compressed set then replace the full dataset in downstream tasks, significantly reducing computational costs while maintaining statistical fidelity. Existing distribution compression algorithms leverage the theory of Reproducing Kernel
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Hilbert Spaces (RKHS) [ to embed distributions into function space. Specifically, these methods minimise the Maximum Mean Discrepancy (MMD) between the true kernel mean embedding of the distribution Px. denoted μx, and the kernel mean embedding estimated with the compressed set, denoted fx. This ensures that the empirical distribution of the compressed set, P Px, remains close to the true distribution x in terms MMD.
Several well-known distribution compression algorithms include
Kernel Herding [3] Kernel
Quadrature 9 Support Points
[10]. Gradient Flow
and
Kernel Thinning [22
Ker-
nel Herding was the first method proposed for distribution com- pression and remains one of the most intuitive approaches. is greedy algorithm that itera- tively constructs a compressed set via gradient descent, optimising super-samples that are not part of the original dataset. Kernel Herding was originally designed compress distributions over labelled data. However, we demonstrate that it can be adapted to compress the joint distribution IP xx of labelled dataset 'D {(x,, y.) X' y using the theory of tensor product RKHSs. This is achieved by optimising a compressed set C == {(e), Új } targeting the Join! Maximum Mean Discrepancy (JMMD) (15). In similar fashion, also adapt the gradient flow approach of (16). which optimises all points in the compressed set jointly.
Figure 1: Compressed set of size m 25 generated by ACKIP (green), initialised with uniformly at random subsample (yellow).
No existing distribution compression method targets the family of conditional distributions Pyjx of labelled dataset. To address the gap, we require the kernel conditional mean embedding (KCME), denoted p The KCME provides way to embed the family of conditional distributions Fy into an RKHS, and a widely used technique for non- paraaarmetticc modelling of complex conditional distributions. Given n labelled samples, it can be consistently estimated with computational cost of (na) 17 18) Despite this high cost, the KCME has been successfully applied in various fields, including conditional distribution testing 18] 19 conditional independence testing [18] 20)
conditional density estimation 21H233. likelihood-free inference [24), Bayesian optimisation 25
probabilistic inference [17
calibration of neural networks (29). reinforcement learning 32) and as consistent multi-class classifier [33). Intuitively, we posit that directly compressing
22
26 28
the conditional distribution should be preferable indirect joint compression, much direct conditional density estimation outperforms approaches based on separate joint and marginal estimates Proofs of all our theoretical results are in Section
34
Our key contributions are:
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.1
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 On (n)) via application the tower property.
This observation enables the development of Average Conditional Kernel Herding (ACKH), linear-time algorithm which constructs a compressed set such that Py|x== Rs Py|x== a.e. x: wrt x Furthermore, in Section 4.3 we propose Average Conditional Kernel Inducing Points (ACKIP) as non- greedy, linear-time alternative that jointly optimises the compressed set 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.

---

2 Preliminaries
In this section we briefly introduce the relevant theory of RKHSs, for more thorough treatment see the various detailed surveys which exist in the literature 35 37
Throughout this work, we consider F,, IP) as the underlying probability space. Let (X, 2) and (V. 3 } be separable measure spaces, and let X : Ω + X' and Y : S2 - y be random variables with distributions Px and Yp,, respectively. We denote the joint distribution of X and Y by IP x and the conditional distribution, in the theorre-theoretic sense of [8]. by PY|x- Given labelled
dataset D :- y=) we refer to the empirical distribution of D Px,.. For compressed set C = (a., ū:) m & n, we instead denote the empirical distribution as P Px,y.
Each positive definite kernel function k : X x X' R induces a vector space of functions from X' to I. known as a Reproducing Kernel Hilbert Space (RKHS) M. denoted by H3. An RKHS H2 is defined by two key properties: (i) For all æ E X. the function k(x,,)
Reproducing Kernel Hilbert Spaces:
+ R belongs to Ng: (ii) The kernel function satisfies the reproducing property, meaning that for all f E Ht and x E X, we have f(x) = (f(-), -<x,-))).. where (.-)H, denotes the inner product in H2. A key property of kernels the concept of universality [38. Intuitively. if a kernel k E (x)) is universal, then for every function S E Co(xX), there exists a function y E Ha that approximates it arbitrarily well. This property satisfied for many common kernel functions such as the Gaussian Laplacian, and Matérn, for example (38)
Tensor Products of Reproducing Kernel Hilbert Spaces: Let x y E be the reproducing kernel inducing the RKHS Hi, and denote H4 @ Hi to be the tensor product of the RKHSs Ha and H4, consisting of functions g X x y + IR Then, for h, E Hr and f, E H, the inner product in M4 & Hi is given by (f 2 g. f & @g),H. == (g.g')H. He (f. f") Under the integrability DC, one can define the joint kemnel mean embedding E H4 & Hi such that Ep (9(X, g E H. 60 Hi 18 The joint kernel mean embedding can be estimated straightforwardly as Jx, = > = k( (y::)) with i.i.d. samples from the joint distribution. The tensor product structure advantageous as it permits the natural construction of tensor product kernel from kernels defined on X' and V This insight is particularly important when X' and y have distinct characteristies that make a direct definition of a p.d. kernel difficult, for example, X = Idd and y = NP.
condition Epx [Rx[X 16(X,X) X)]
< OC, Bp, (( JX.Y == E2 x [(X, ()(Y))YY
(px.Y,9)H..s) for all
Given additional random variables X' : Ω + X, Y': ; S + y, and the embedding ,' of Px one can define the Joint Maximum Mean Discrepancy (JMMD) [5] as
IMMD(PX.y,xx.r)
||xx μxx y 1H
For a particular class of characteristic tensor product kernels [39], the mapping Fx.y + jx, is injective [40]. Hence, by the virtue of Theorem 5 (2] it is the case that JMMD x,Y, Px,,) ||xx, - p 11 = 0 if and only if P = Px
Conditional Kernel Mean Embedding: Under the integrability condition Epy [V[[Y, Y) < co, the kernel conditional mean embedding (KCME) of PrІx is defined as Jyix == Eey, [(Y, X where Jy|x : Ω - H4 is an X-measurable random variable outputting functions in H4. Similar to
the unconditional case, for any f Hi, it can be shown that Eyy [f(Y) | X] 0.5. (f. H4
The KCME can be written as the composition of a deterministic function Fy : + Hi and the random variable X Ω + X, i.e. Jylx Frjx X (Theorem 4.1, 1 For consistency in notation, throughout the remainder of this work, whenever we refer to the KCME fY|x, we mean Fylx- The KCME can be estimated directly [18 30 using i.i.d. samples from the joint distribution D as
pPix = Σ M...))W,
where the superscript D refers to the data used to estimate fY|x, we define W (K + +1)-1 [K]; = k( azy), i, = 1, I,, and À > 0 is a regularisation parameter. Maximum Conditional Mean Discrepancy: Given two conditional distributions IP P and Py with KCMEs μal and py the Maximum Conditional Mean Discrepancy (MCMD) was defined
3

---

by [8] as function of the conditioning variable a E X, which returns a metric on Pyjx-a and Fy that
MCMD [y Py (a) == |lyyx== MY|x'==llx.
In the following sense sense, the MCMD is a natural metric on the space of conditional distributions: Theorem 2.1. (Theorem 5.2. (18) Suppose 1 ; V x y + R is characteristic, that Px and Fx are absolutely continuous with respect to each other, and that P(- X) and IP(- X') admit regular versions. Then MCMD
) if and onty if. for almost all E X wr x (or ))), we have Py|x== (B) = (B) for all B E y.
(+) 0 almost everywhere wrt Px (or Px)
Existing distribution compression methods focus on unlabelled data, where the goal is approximate Px using smaller representative that minimises the Maximum Mean Discrepancy (MMD). Perhaps the most intuitive of these is Kernel Herding B 41,, which greedily constructs compressed by iteratively optimising points that minimise the MMD. While simple and interpretable, its greedy nature can lead to suboptimal solutions, motivating alternatives such Gradient Flow [Л]. which jointly optimises all points via gradient descent, and Kernel Thinning [3 [4, which restricts the compressed set to a subset of the original data to support theoretical guarantees. Despite these advances, existing approaches target unlabelled distributions. contrast, this work introduces algorithms for joint and conditional distribution compression. For additional discussion of related work see Section A.
Related Work:
Joint Distribution Compression
Given labelled dataset D, may be interested in compressing the joint distribution Px,,, rather than the marginals Px, Py.
3.1 Joint Kernel Herding
By inducing an RKHS H4 @ H4 with the tensor product kernel k(..))((:.), one can modify the Kernel Herding 3 algorithm to instead target the joint distribution. First, we assume that ||( -)(,,, @H, R for all E X and y E y. where R is a constant. This condition holds for commonly used stationary kernels such as the Gaussian, Laplace, and Matérn kernels. Then, assuming we are at the (m + 1)th iteration, having already constructed compressed set of size m, the next pair is chosen as the solution to the optimisation problem
C = [(ē,, ú 1=
arg min (a. xxy m
1
Σ m,))yy D3) -E (P(ea//))xxx [k(x, x (y y')]
We refer to this algorithm as Joint Kernel Herding (JKH). The optimisation problem in can be interpreted as reducing at each iteration the JMMD Px,, Px,y); see Section B.2
3.2 Joint Kernel Inducing Points
The greedy optimisation approach of JKH is convenient heuristic which focuses computational effort on optimising one new pair at time while previously selected pairs are fixed. However, this first
strategy may give poor solutions, it never revisits adjusts earlier selections. Instead, select an initial compressed set of m pairs through uniformly at random subsampling of D, followed by refining all pairs jointly. Going forward, we refer this algorithm as Joint Kernel Inducing Points (JKIP), noting that it may be viewed as a discretised Wasserstein gradient flow (II).
target the JMMD (P x,y, Px,Y) by solving the optimisation problem
m
arg min Xxy)
Σ +1==1
m Σ (a yf wxx [M a') y
m
via gradient descent. In the general case, one cannot compute the expectation above, hence we instead target its empirical alternative, namely JMMD(Pxxyx Px.Y). Defining X = [x1, 22, ..... xx. T.

---

y= y1. M2.
ynl", , X = (81, "t....,,,............. and Y = 181 Ø2.... .0ml this reduces to
targeting
2
C (x, Y) = Tr xx mn
(K x x
(4)
m²
where [K x == k( x = k( [Tyyyy == 1i: Uj), and yy = (ūr Vj). One might initially assume that JKIP is more computationally expensive than JKH due to its higher cost per gradient step, but this not the case. In fact, to construct compressed set of size m, both JKH and JKIP have time complexity of O(mn + m²); see Section D.2.1 and D.2.2
From Joint to Conditional Distribution Compression
4.1 The Average Maximum Conditional Mean Discrepancy
In Section 2 we recalled the MCMD, which a function of a X' that outputs a metric on the conditional distributions Py|x=== Pyjx'== with fixed conditioning values. However, for the purposes of distribution compression, we require discrepancy measure that applies to entire families of conditional distributions Py|xx Py-jx-. Prior work has introduced the discrepancy
Ex-Px [|]иУ|ж== -y H.
which was independently proposed as the Average Maximum Mean Discrepancy (AMMD) in and the Kernel Conditional Discrepancy (KCD) in [9]] Throughout this work, we will refer as the KCD. We introduce more general alternative, and show it is a proper metric: given an additional
random variable X + X' with distribution Fx-, we define the Average Maximum Conditional Mean Discrepancy (AMCMD) as
AMCMD Pr ==
BEexxxx [|lлटx=== py 1
(6)
In the above definition, the expectation is taken with respect to a distinct probability measure Px- # Px,PP Pr,, which broadens its applicability compared to the KCD. See Section C.2 for an illustrative example.
The following theorem establishes that the AMCMD is indeed a proper metric.
Theorem 4.1. Suppose that y x y - T.. is characteristic kernel, that TP x, Pxx, and x. are absolutely continuous with respect each other, and that TP(- X) and TP(- X') admit regular if and only if. for almost all x E X wrt Px., versions. Then, AMCMD [xx,, Exx,PPyxx PY,,, | Fy|x== = xx (B) for all B
Moreover, assuming the Radon-Nikodym derivatives dEx- dpx. de are bounded, then the trian- &x oFx' pxx" gle inequality is satisfied, i.e. AMCMD [Px-, Pylx, & AMCMD (MMMDDPxx,PyIS Py:xx AMCMD Px-, [. Remark 4.2. The boundedness condition on the Radon-Nins -ikoodm derivative may intuitively understood as condition on the relative heaviness of the tails of the distribution Px- compared to Px. For example, if x N(,, and Px = NN, o²), then dpx= is bounded whenever o²
dFx
Given sets of ii.d samples {x Fx., N {(x,, yi) ((a), v ~ Fx,., we define a plug-in estimate the AMCMD" as
Px,., and M
2
AMCMD Prxx,Prix, [Vxx q
A
M -
Hi
and derive a closed form expression as follows:
Lemma 4.3.
AMCMD2 [Px,, x
q
q
5

---

where, for example, we have defined [Kx-x-ls = x()',x"), [LYr- = 1yy Vj). and Wx'x = (Kx'x Am_
This estimate is O(n + m + q(22 + m²)) to compute. As a corollary of Theorem 4.5 in 19), we establish its consistency in the special case that X = X' X, which corresponds to the regime under which our conditional distribution compression algorithms will operate.
Corollary 4.4. Assume that k((;-) and -(: are bounded, k(.,-) is universal, and let the regularisa- tion parameters An and Am decay at slower rates than On (n22)/2 and O respectively, Then, AMCMD [xx, PPx,
2 AMCMD xPx, Pyix, Py-xx] as m. q + oc.
Remark 4.5. The conditions in Corollary 4.4 ensure that fayx and fy converge Jyix and Jy*x respectively in I (,2 xx; H4) norm, that is, the norm of the space of square Px iiitteega Hi-valued functions [1]
Remark 4.6. The conditions on i and are satisfied by many common choices. For example, with continuous conditional distributions, both be Gaussian kernels; for discrete conditional distributions, can be replaced with an indicator kernel (3].
4.2 Average Conditional Kernel Herding
We now introduce Average Conditional Kernel Herding (ACKH), greedy algorithm that constructs
a compressed set targeting the AMCMDD(Ps Fyjx, Fr]x). The ACKH objective is derived by
expanding the squared norm in (6). and ignoring the term which is invariant wrt the compressed set.
Assuming we are at the (m + 1)th iteration, having already constructed the compressed set C = { Uj )- we expand the compressed set C C. U (x, y) by solving
|
2
A4 PP K -
arg min w.y
(8)
Hi
Hi
As we do not have access to JalI and Px, we must estimate this objective; this is equivalent to targeting the AMCMD² Py |y]x] Naïvely, one might assume that we must estimate J using D, incurring high computational cost of Onn²). The following result allows us to avoid this: Lemma 4.7. Let h X Hi vector-valued function, then
Ex-rx [UYIX= Mxx)) H.
(( [x))
Remark 4.8. If we let h(x) = [ then Lemma 4.7 eliminates the need to explicitly estimate JY|x 8 and hence, the cost of estimating the objective reduced from O(n3) to (()).
Even after applying Lemma 4.7 we still have an expectation in ( which we may not be able to compute general. Estimating this expectation using DD we obtain the closed form objective
2 n where we define [x)), = k(o,, -2), 1,... j 1..... m, [x)); = k( R,). j 1,..., m. and W(x) = (K(x) AT)-1, Analogous definitions hold for the response kemnel 1(. )), yielding matrices L(y) E Raxm and i(y) Rmxm To construct compressed set of size
cl v) = T1
m, ACKH can be shown to have an overall time complexity of O(m" + m²n); see Section D.2.3
4.3 Average Conditional Kernel Inducing Points
Unlike JKH, where updates depend only the newest pair in the compressed set, the presence of an inverse the objective (9) prevents similar simplification. This leads to quartic dependence of ACKH on the compressed set size m, which is a fairly significant limitation. By instead optimising each pair in the compressed set simultaneously. we can reduce this to just cubic dependence on m.
TThouuhh the method of bordering (43), it technically possible to update the inverse of a growing matrix, minimising re-computation. Unfortunately, bordering is highly numerically unstable procedure, and kernel matrices often very ill-conditioned in practice.

---

We refer to this algorithm as Average Conditional Kernel Inducing Points (ACKIP), solving the optimisation problem
2 HH
[ [ x (v)}
arg min c
2x v') (1)
(10)
over each pair in C = (x, Y) via gradient descent. Once again, even after applying Lemma 4.7 to
(10) we still retain an expectation which in general is difficult to compute. Estimating this ecoectatuion using D, we obtain the closed form objective
J (X Y
Tr x
x X Wx
W ( xxxxxx) (11)
2 (Ly
72
where W x = (K x
xxxx + 11)- To construct compressed set of size m, ACKIP has an overall complexity of O(m + m m)) i.e. a factor of m faster than ACKH; see Section D.2.4
5 Experiments
Building on the experimental setup of Kernel Herding 3 we demonstrate how the methods proposed in this paper can be applied to compress the conditional distribution. We report the root mean
square error RMSE(C)= == v Σ. (B(M(Y X = =.] 1
across a range of
test functions h : y + E. This aligns with the standard applications of the KCME [3:33] where one estimates the conditional expectation of a function of interest h. When the exact value of the conditional expectation unavailable, we approximate B[h(Y) X = æz.] via its full-data estimate, (1 h)H,- Note that when h is the identity function, the estimate reduces to the familiar regression setting i.e. B| XJ. and when h is indicator function, it corresponds estimating class-condie consitondiiio probabilities e.g. P(Y = 0 X). For full details of the experiments. including results on additional test functions omitted from the main text due to space constraints, see Section C
5.1 Matching the True Conditional Distribution
In general, the expectations in 2 k and I are Gaussian, and we let Px (H, o²) and PyІx = -aaas +
and (TO) must be estimated. However, when the kernels
x,)?) for μu, au, a1 E R C.3 for details. We construct
and 0² o2 > 0, the integrals can be evaluated analytically. See Section
PPx x Py|x achieved by each method. Figures 2 and 3 highlight the advantages of directly targeting the conditional distribution, with ACKH and ACKIP achieving lower AMCMD compared to JKH and JKIP. Additionally, in the case of ACKIP versus ACKH, it demonstrates the superiority of joint optimisation over herding, where the inability to revisit previous selections limits ACKH's performance in comparison to ACKIP. Moreover, we can see that the reduced AMCMD achieved by ACKH and ACKIP translates to improved performance in estimating conditional expectations across variety of test functions.
compressed sets of size = 500, and compute the AMCMD2
hly +y
htyi -yny)
Mly - 11
AMCMD- (agp=lly.ee Py pa By Al
10'11
RMSE
Sarpalyy my
3.7
147
Campressed Set
Campressed
Compressed
Campressed
Figure 2: Results for the true conditional distribution compression task with parameters set as ag = -0.5, 01 = 0.5, = 1, o² = 1, and o² = 0.5. The AMCMD² (first plot). and the RMSE across three test functions, versus the size of the compressed set reported. For JKH (orange), JKIP (red). ACKH (blue), and ACKIP (green), we display the median performance (bold line) with the 75th percentiles (shaded region) over 20 runs. The error of random sampling (black) over 500 runs is also plotted for comparison.
7

---

hly) -y
sinyys
hyy =
Rly - 1
400P
RASE
ACRP
ACOP
ACRIP
Figure 3: Results of the true conditional distribution compression task for compressed sets of size m 500. The RMSE across variety of test functions is reported, with the IQR highlighted for each method. Outliers are calculated as being above Q3 + 1.5IQR and below Q1 1.5IQR.
5.2 Matching the Empirical Conditional Distribution
In this section, we present experiments targeting the empirical conditional distribution of synthetic and real-data. Across all datasets, generate or subsample down to n 10, 000 pairs, split off 10% for validation, 10% for testing, and construct compressed sets up to size m = 250.
5.2.1 Continuous Conditional Distributions
Real: We the Superconductivity dataset from UCI 44 Superconductivity is composed of d 81 features relating to the chemical composition of superconductors with the target being its critical temperature 45 In Figure 4 3 we that ACKIP achieves the lowest RMSE across each of the test functions, with ACKH in second for all but one. We also note that JKIP achieves favourable performance versus JKH.
myl -y
myn- -snty)
hly
hty) - 11yxo)
RMSE
Aandon
101
30
Compressed Set
Compressed
Size
Comoressed Set
Compressed Size
Figure 4: RMSE versus size of compressed set for the Superconductivity data; the RMSE is calculated against the full data estimates of E[A(Y) X = æi} as the true values are not available.
Myy) my
My) = sinly)
hly) -
Myt = 01
RAMSE
ADOP
ACKP
ACCP
Figure 5: RMSE achieved by compressed sets of size 250 constructed by each method for the Superconductivity data. The IQR is highlighted for each method with outliers calculated as being above Qa + 1.5IQR and below Q 1.5IQR.
Synthetic: We design a challenging dataset with a highly non-linear feature-response relation- ship and pronounced heteroscedastic noise, referring to it as Heteroscedastic going forward. Let
8

---

Px = 23) and = -( with f(z) = a, exp (- (x ci)2) and d²(x) := of + |o3 sin(æ)]. Figure compares a compressed set constructed by ACKIP, with the random sample which initialised the optimisation procedure. It demonstrates how random sampling fails to adequately represent key areas of the data cloud, and how ACKIP can construct a better representation. In Figures Fadd Twe we see that ACKIP attains the lowest RMSE across three of the four test functions. For the remaining function, all methods exhibit relatively similar performance, We also note that JKIP outperforms achieves similar performance versus JKH across the test functions.
6,
x20-1
bly] =y
Bly) sin(y)
=
Mty Lgscot
RH
RMSE
10'
Compressed
Compressed
Compressed
Compressed
Figure 6: RMSE versus size compressed set for the Heteroscedastic data with parameters set as 3, 3,, -6] = [1, 0.1. 0.5] c [-5, 2, 2, 5] of 0.1 and o 0.75. The RMSE is calculated against the true value of the conditional expectations: the performance of the full data (purple) is hence also highlighted here.
x00
my
My) sin())
fly) m
Myl =
Randon
RMSE
ADOP
ACXP
ACOP
Figure 7: RMSE achieved by compressed sets of size m = 250 constructed by each method for the Heteroscedastic data. The IQR is highlighted for each method with outliers calculated as being above Q3 + 1.5IQR and below Q - 1.5IQR.
5.2.2 Discrete Conditional Distributions
Conditional distributions may also be discrete, in classification settings where responses take of C' distinet values E {0, 1........ C). In such cases, applying an indicator kernel on the response space enables the KCME serve as consistent multi-class classifier, in contrast methods like SVCs and GPCs 333. The use of the indicator kernel renders standard moddient-based optimisation inapplicable on the response space, necessitating an alternative optimisation strategy (see Section C.1.3 for details). Figure illustrates the strong performance of ACKIP on challenging, synthetic, imbalanced four-class classification dataset, which we refer to Imbalanced. We see that the KCME, trained with the compressed set constructed by ACKIP, estimates the cass-conditional probabilities with accuracy that very closely matches that of the full dataset at just 3% of the size. contrast, figure also exposes the limitations of the herding approach: ACKH performs worse than random on three of the four classes, and JKIP outperforms JKH on three out of the four classes. For full details on Imbalanced, and additional experimental results, including MNIST,
Section C.1.3

---

x10
hly) 1)
hly) 1
hly) 1y)
X10
h(y) 1yy
hal Late
Rancom
22-
1.-
RMST
2.0
1.5-
1.-
14
10"1
10
ACEP
XOXP
14
Figure 8: RMSE achieved by compressed sets of size 250 constructed by each method for the Imbalanced data. The RMSE is calculated against the true value of the conditional expectations: the performance of the full data (purple) is hence also highlighted here. The IQR is highlighted for each method with outliers calculated as being above Q3 + 1.5IQR and below Q1 1.5IQR.
Discussion
Applicability: ACKIP generates a compressed set that enables efficient estimation (from ((n)) to O(m² + +m² m)) and evaluation (from On?)) (m²)) of the KCME while maintaining a close approximation to the true KCME in terms the AMCMD. The KCME is widely used across various applications [1733] despite its original (n²) computational cost. By reducing this to (()). whilst impacting empirical performance minimally, our approach may significantly expand the range of scenarios where the KCME can be practically applied. In particular, wherever one may have used random subsample of size m to estimate the KCME with cost O(m²). ACKIP can be inserted, where running even just a few iterations of the algorithm increases the efficacy of the random sample at just O(nm² additional cost.
Limitations: Our algorithms currently lack formal convergence guarantee. Although empirical results consistently show convergence across a wide range of experimental settings, including both real-world and synthetic conditional distributions, continuous and discrete, a rigorous theoretical proof remains open. In practical terms, our approach depends on computing kernel gradients, which may be unsuitable for data domains where gradients ill-defined or difficult to interpret, such as graphs or text 44 [47] In such cases, gradient-free alternatives inspired by Kernel Thinning 122 may be preferable to versions of JKH and ACKH that greedily select optimal sample pairs directly from the existing dataset (see Algorithms 5 and 6).
7 Conclusions
We showed that existing distribution compression methods can be extended to target the joint distribution, introducing JKH and JKIP. In particular, JKIP removes the heuristic limitations of greedy optimisation by jointly optimising the compressed set, while preserving the same computational cost. We then presented the AMCMD, an extension of the MCMD that defines a proper metric on families of conditional distributions. We derive a closed form estimate of the AMCMD and demonstrate that it can be consistently estimated in the regime of our compression algorithms. Then, leveraging the AMCMD, we proposed ACKH and ACKIP, two linear- time conditional distribution compression algorithms that are the first of their kind. Experimentation across range of scenarios indicates that it is preferable to compress the conditional distribution directly using ACKIP or ACKH, rather than through the joint distribution via JKH or JKIP. Moreover, we see that the greedy optimisation approach of ACKH limits its empirical performance, and increases its computational cost, versus ACKIP. Finally, we also note that JKIP consistently outperforms JKH across our experimental settings. This work opens up numerous promising avenues for future research; for detailed discussion of potential directions, see Section A.2
8 Acknowledgements
We would like to thank the EPSRC Centre for Doctoral Training Computational Statistics and Data Science (COMPASS), EP/S023569/1 for funding Dominic Broadbent's 's PhD studentship.
10

---

References
[1] Aronszajn. Theory of reproducing kernels. Trans. Amer, Math. Soc., 68:337-4044 -044 1950. doi: 10.2307/1990404.
[2] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(25):723-773, 2012. URL Utt.http:///mml. wwwp:ragg/ppp//aeeeeeee v13/
/ gretton12a html
[3] Yutian Chen, Max Welling, and Alex Smola. Super-samples from kemel herding. In Proceedings of the Twenty-Sixth Conference on Uncertainty Artificial Intelligence, UAI'10, page 109-116, Arlington, Virginia, USA, 2010. AUAI Press. ISBN 9780974903965.
[4] Ferenc Huszár and David Duvenaud. -weighel herding is bayesian quadrature. In droceedings of the Twenty-Eighth Conference on Uncertainty Artificial Intelligence, UA page 377-386, Arlington, Virginia, USA, 2012. AUAI Press. ISBN 9780974903989.
[5] Francis Bach. On the equivalence between kernel quadrature rules and random feature expan- sions. J. Mach. Learn. Res., 18(1):714-751, January 2017. ISSN 1532-4435.
[6] Ayoub Belhadji. Rémi Bardenet, and Pierre Chainais. Kernel quadrature with dpps. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc Buc, E. Fox, and R. Garnett, edi- tors, Advances Neural Information Processing Systems, volume 32. Curran Associates. ptpppppppp///iieeee//// Inc.. 2019. URL utL/sttts://prrceedinge neurips. cc/ http:pppp.pppppp...aaaaaaapppp/e /ttp///ee..llleepp/////////////1 (11eee00552aaab55666600222111122
[7] Satoshi Hayakawa, Harald Oberhauser, and Terry Lyons. Positively weighted kernel quadrature via subsampling, 2022. URL htttt::///rxxii>> wwwggaab//2110.000 http::://arri..oorr/a////1/101
09597
[8] Satoshi Hayakawa, Harald Oberhauser, and Terry Lyons. Sampling-based nyström approxima- tion and kernel quadrature, 2023. URL
09511
[9] Ethan N. Epperly and Elvira Moreno. Kernel quadrature with randomly pivoted cholesky. ArXiv, abs/2306.03955, 2023. URL. httpss//app..smmmm...cccooooooro
259095887
[10] Simon Mak and V. Roshan Joseph. Support points, 2018. URL http::tt///aii..rrr//
1609.085 01811
[11] Michael Arbel, Anna Korba, Adil Salim, and Arthur Gretton. Maximum mean discrepancy gradient flow, 2019. |ttppss/://arr org abs//196. 04370
[12] Raaz Dwivedi and Lester Mackey. Generalized kernel thinning, 2021. URL https://arxi: org/abs/2110 01593
[13] Raaz Dwivedi and Lester Mackey. Kernel thinning. Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 1753-1753. PMLR, 8 2021. URL
https://proceeddnng: mlr ptress/vv33//wiivdi2211 html
[14] Abhishek Shetty, Raaz Dwivedi, and Lester Mackey. Distribution compression in near-linear time, 2022. URL http::tttt///aat wwwriii.org///oo abs htabb///11.00000 07941
[15] Mingsheng Long, Han Zhu, Jianmin Wang, and Michael I. Jordan. Deep transfer learning with joint adaptation networks. In Proceedings of the 34th International Conference Machine Learning Volume 70, ICML' 17, page 2208-2217, JMLR.org, 2017.
[16) Zonghao Chen, Toni Karvonen, Heishiro Kanagawa, François- Xavier Briol, and Chris. J. Oates. Stationary mmd points for cubature, 2025. URL htt.::htts://rttsee org/ abs/2505 2505. 20754
[17] Le Song, Jonathan Huang, Alex Smola, and Kenji Fukumizu. Hilbert space embeddings of conditional distributions with applications to dynamical systems. In Proceedings of the
26th Annual International Conference Muchine Learning, ICML '09, page 961 961-968, New
York, NY, USA, 2009. Association for Computing Machinery. ISBN 978160558111.. doi: 10.1145/1553374.55555 15534977
URL https: http://oo..oggg/e// 1151111533/1111111 1553497
11

---

[18] Junhyung Park and Krikamol Muandet. A thesurc- approach to kernel conditional mean embeddings. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 21247-21259, Curran Associates, Inc., 2020. URL. http:http::///ooeeaa httpttpps//ppoceeednnge httpp//ooeeeiinneeeeeee..sr..pee cc/paper....... Files/paper 2020/file/f34m0 105.00066666666666999966661000.0
pdf
[19] J. Park, U. Shalit, B. Schölkopf. and K. Muandet. Conditional distributional treatment effect with kernel conditional mean embeddings and u-statistic regression. In Proceedings of 38th International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 8401- 8412. PMLR, July 2021. URL httttss://proceeddnngg mlr
pxess//139/park21c hhmll
[20] Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kerne--based conditional independence test and application in causal discovery. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligecee UI page 804-813, Arlington, Virginia, USA, 2011. AUAI Press. ISBN 9780974903972.
[21] Ingmar Schuster, Mattes Mollenhauer, Stefan Klus, and Krikamol Muandet. Kernel condi- tional density operators. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 993-1004. PMLR, 26-28 Aug 2020. URL attpps//proceeddnggs
wwwpeeiiinnn.........mm.mmomerem mlr www.s/rressssiv//eeee httpe//v00/////// hwtp//srssssssaaaaeeaaese /tress//100//chhuste22.... html
[22] Jake D Spiteri. Nonparametric Estimation with Kernel Mean Embeddings. PhD thesis, Bristol Doctoral College, School of Mathematics, 2024.
[23] Eiki Shimizu, Kenji Fukumizu, and Dino Sejdinovic. Neural-kernel conditional mean embed- dings, 3 2024. URL httph:ttt///xiiii wwwpixiiv.org//bb org/abs/25 //////bb///0.... 2403. 10859
[24] Kelvin Hsu and Fabio Tozeto Ramos. Bayesian learning of conditional kernel mean embeddings for automatic likelihood-free free inference. In International Conference on Artificial Intelligence and Statistics, 2019. URL httph:h/ppppp www.nticschooiieeeeoee wrrpeeccooaaaooorrrrrrruuuuusll wrg/Corrg/CDDDCD ID: 67855374
[25] Sayak Ray Chowdhury, Rafael Oliveira, and Fabio Tozeto Ramos. Active learning of conditional mean embeddings via bayesian optimisation. In Conference on Uncertainty in Artificial Intelligence, 2020. URL https:s::://ap. wew.aapiisemaaiicccoll.a.rrr org/ CorpusID: 220623530
[26] Le Song, Byron Boots, Sajid M. Siddiqi, Geoffrey Gordon, and Alex Smola. Hilbert space embeddings of hidden markov models. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML. 10, page 991-998, Madison, WI, USA, 2010. Omnipress. ISBN 9781605589077.
[27] Le Song, Arthur Gretton, and Carlos Guestrin. Nonparametric tree graphical models. In Yee Whye Teh and Mike Titterington, editors, Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pages 765-772, Chia Laguna Resort, Sardinia, Italy, 5 2010. PMLR. URL https://proceedings. mlr press/v9 v https///v///gggaaaa/ html
[28]
Le Song, Arthur Gretton, Danny Bickson, Yucheng Low, and Carlos Guestrin. Kernel belief propagation. In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 707-715, Fort Lauderdale, FL. USA, 11-13 html
Apr 2011. PMLR. URL
mll http:/mmww...eee///////g//eeee//
[29] Spencer Young, Cole Edgren, Riley Sinema, Andrew Hall, Nathan Dong, and Porter Jenk- ins. Beyond calibration: Assessing the probabilistic fit of neural regressors via conditional congruence, 2024. URL URL/attps://ariit wwwpziivv.rr/ree abs /wwp/////.... 12412
[30] Steffen Grünewälder, Guy Lever, Arthur Gretton, Luca Baldassarre, Sam Patterson, and Massi- miliano Pontil. Conditional mean embeddings as regressors. ArXiv, abs//205.4661 4656, 2012. URI.
l.m. www. Stt//oorpuID::1471111
12

---

[31] Yu Nishiyama, Abdeslam Boularias, Arthur Gretton, and Kenji Fukumizu. Hilbert space embed- dings of pomdps. Uncertainty in Artificial Intelligence Proceedings of the 28th Conference, UAI 2012, 10 2012.
[32] Byron Boots, Arthur Gretton, and Geoffrey J. Gordon. Hilbert space embeddings of predictive state representations. In Proceedings of the Twenty-Ninth Conference on Unceriainty in Artificial Intelligence, UAI' 13, page 92-101, Arlington, Virginia, USA, 2013. AUAT Press.
[33] Kelvin Hsu, Richard Nock, and Fabio Ramos. Hyperparameter learning for conditional kernel mean embeddings with rademacher complexity bounds, 2018. URL httpp::/aaxii..... abs/1809.000 00175
[34] Rafael Izbicki and Ann B. Lee. Nonparametric conditional density estimation in a high- dimensional regression setting. Journal of Compulational and Graphical Statistics, 25(4):
1297-1316, October 2016. ISSN 1537-2715. doi: 10. 101000000016000 (0000666000020111099500000000000 URL
http://dx.co wttp://ddoooooo//o/o/oooooooooot 10800 10010000.61000.... 2015. 1094393
[35] Alain Berlinet and Christine Thomas-Agnan Reproducing Kernel Hilbert Space in Prob- ability and Statistics. Springer US, 01 2004. ISBN 978-1-4613-4492-7,
doi: 10.1007)
[36] Charles A. Micchelli and Massimiliano Pontil. On Learning Vector-Valuee Functions. Neural Computation, 1771) 01 2005. ISSN 0899-7667. doi: 10.116208997655530002.
URL httpp::////oooooo 1ttp:/11..1122999911111 100.11666//6697605000000
[37] Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, and Bernhard Schölkopf. Kernel mean embedding of distributions: A review and beyond. Foundations and Trends in Machine Learning, 10(1-2)111411 2017. ISSN 1935-8245. doi: 10. 10.1561/22000000660. Utthttp
7/dx. ooooorgg/11 10. 1ww1 150220000000
[38] Claudio Carmeli, Ernesto De Vito, Alessandro Toigo, and V. Umanità. Vector valued repro- ducing kernel hilbert spaces and universality. Analysis and Applications, 08, 11 2011. doi: 10.1 10.1142/502195305 1000000020050000005000000
[39] Bharath K. Sriperumbudur, Kenji Fukumizu, and Gert R.G. Lanckriet. Universality, characteris- tic kernels and rkhs embedding of measures. Journal of Machine Learning Research, 12(70): 2389 2410, 2011. URL http::/jjmll hetpiirlorgg/ppeeeeeee wwwgpapers/aaaeeeo
wwapers/viil. /v1// sr www.prrruuuuuuura 1aa html
[40] Zoltán Szabó and Bharath K. Sriperumbudur. Characteristic and universal tensor product kernels. Journal of Machine Learning Research, 18(233):1-29, 2018. URL http::/jmml
org/papers/v18/17 19-88/17799221 492. html
[41] Francis Bach, Simon Lacoste-Julien and Guillaume Obozinski. On the equivalence between herding and conditional gradient algorithms. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML'12, page 1355-1362, Madison, WI,
USA, 2012. Omnipress. ISBN 9781450312251.
[42] Ziyi Huang, Henry Lam, and Haofeng Zhang. Evaluating aleatoric uncertainty via conditional generative models, 2022. URL httptttt////xiv....t http:::///aaiii.oor/bb//////2/ 240p//2227200027777
[43] D.K. Faddeev and V.N. Faddeeva. Computational methods of linear algebra. A series of undergraduate books in mathematics. W.H. Freeman, 1963. URL http::ttt:::///t htttlp:://bboos.ggge http:/booooo..oeeeeee co. g..u/bbokksi.dkss.00R....
[44] Kolby Nottingham Markelle Kelly, Rachel Longjohn. The uci machine learning repository.
/ ics. www.cc...........o uci.
[45] Kam Hamidieh. A data-driven statistical model for predicting the critical temperature of superconductor, 2018. URL htttps/////axxii wwtp://w.wwg//////0/000 10260
[46] Thomas Gärtner, Peter A. Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Annual Conference Computational Learning Theory, 2003. URI.
https: https://api. semanticscholar. .rrg hetg/CCrpuII:::000 10856944
13

---

[47] Huma Lodhi, John Shawe-Taylor, Nello Cristianini, and Christopher Watkins. Text Classification using String Kernels. In T Leen, T Dietterich, and V Tresp, ed- itors, Advances in Neural Information Processing Systems, volume 13. MIT Press. 2000. URL. httts://prroeeedins....rtr http://cawaaa..rrrrrprppppppeppa http:pparrflae/aaaeaapapee wttp://ee//pppe2/0/////eeaee Saccl445s46c11011523876666663333
pdf
[48] Dino Sejdinovic, Bharath Sriperumbudur, Arthur Gretton, and Kenji Fukumizu. Equivalence of distance-base and bahs-based statistics in hypothesis testing. The Annals of Statistics, 41(5), October 2013. ISSN 0090-5364. doi: 100.1111000000...11100 URL http: bett::/dss //tx. doi org/10 2214/13-A0S111
[49] Noveen Sachdeva and Julian McAuley. Data distillation: A survey, 2023, URL https
//arxiv.org abs/2301 04272
[50] Yong Ren, Jialian Li, Yucen Luo, and Jun Zhu. Conditional generative nomentt-mtchiin net- works. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, page 9936-2944, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 978151083889,
[51] Pengfei Ge, Chuan-Xian Ren, Dao-Qing Dai, and Hong Yan. Domain adaptation and image classification via deep conditional adaptation network, 2022. httplttsss//axivv. abs/
2006.07776
[52] Tushar and Souvik Chakraborty. Deep physics corrector: A physics enhanced deep learning architecture for solving stochastic differential equations. Journal of Computational Physics, 479:112000 April 2023. ISSN 0021-9991.
doi: 10. N0.1016/j.jcp.2023.. 110044. URL http
//dx. faxx.doi.co org/ 10. 1016/j.jcp.... 2023. 112004
[53] Boya Hou, Sina Sanjari, Nathan Dahlin, Alec Koppel, and Subhonmesh Bose. Nonparametric sparse online learning of the koopman operator, 2025. URL https://arxiv. org/abs/2205 07432
[54] Guy Lever, John Shawe-Taylor Ronnie Stafford, and Csaba Szepesvari. Compressed conditional mean embeddings for model-based reinforcement learning. In AAAI Conference on Artificial Intelligence, 2016. URL/httss://apt http://ppp..emmaticcchollllala org/ Corpus I:: 60597677
[55] Tamim El Ahmad, Lue Brogat-Motte, Pierre Laforgue, and Florence d' Alch'e Buc. Sketch in, sketch out: Accelerating both learning and inference for structured prediction with ker- nels. ArXiv, abs/2302.10128, 2023. Utthttps:://aat stt.aapssstaattccollaaaaaaa PrrgCoorusII/ 257038736
[56] Michael W. Mahoney. Randomized algorithms for matrices and data, 2011. URL https
7/arxiv. www.:/gg////////ee/e /t///1104.5550 5557
[57] Boya Hou, Sina Sanjari, Nathan Dahlin, and Subhonmesh Bose. Compressed decentralized learning of conditional mean embedding operators in reproducing kernel hilbert spaces. In Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence, A.AA/23/AAA223/AAAT332 AAAI Press, doi: 10.1609/aaai.vv377..oo 2375.. URL https: org/
2023. ISBN 978-1-57735-880-44 10. 1209/699/aa 2t7p://7............... 25956
[58) Albert Gong, Kyuseong Choi, and Raaz Dwivedi. Supervised kernel thinning, 2025. URL
https://arxee org/ abs//410/ 13749
[59] Masashi Sugiyama, Matthias Krauledat, and Roburt Müller. Covariate shift adaptation by importance weighted cross validation. Journal of Machine Learning Research, 8(35):985-1005 2007. http://t:///m1t http://hhaa..rrrrppppp////////// http:///www/uggaaaaaaaaa00 html
[60] Jose G. Moreno- Torres, Troy Raeder, Rocío Alaiz-Rodríguez, Nitesh Chawla, and Francisco Herrera. A unifying view on dataset shift in classification. Pattern Recognition, 45(1):52) (111):521300 2012. ISSN 0031-3203. doi: http:://oo.oooyoll..of/////oooop
URL. hhttps
14

---

[61] Fuzhen Zhuang. Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong, and Qing He. A comprehensive survey on transfer learning, 2020. URL https 7/arxiv.org www.://gggaabbb//eeeeeo wtt.aa/s/....eee/ee//e/
[62] Abolfazl Farahani, Sahar Voghoei, Khaled Rasheed, and Hamid R. Arabnia. A brief review of domain adaptation, 2020. URL/https://aaxiy org/ wwt.a/10..c.moooo 009978.
[63]
Jiayuan Huang, Arthur Gretton, Karsten Borgwardt, Bernhard Schölkopf, and Alex Smola. Correcting sample selection bias by unlabeled data. In B. Schölkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems, volume 19. MIT Press, 2006. URL/ttttss:/pprrceeiinng neurips wwtppcpppppppeeee httpappr.iilsepppperrreeeeeeeeee file/a2116aa7 httpa//aaaaae0eeeeeeeeeeeaaaaaaa
pdf
[64] Liwen Ouyang and Aaron Key. Maximum mean discrepancy for generalization the presence of distribution and missingness shift, 2022. URL/attps://arxxv.coo org/ abs//a111 10344
[65] Hongliang Yan, Yukang Ding. Peihua Li, Qilong Wang, Yong Xu, and Wangmeng Zuo. Mind the class weight bias: Weighted maximum mean discrepancy for unsupervised domain adaptation, 2017. URL hattps:/aare /ttp:v//axvvvvv. org/ abs 2000b./1000000000 00609.
[66] Wei Wang, Haojie Li, Zhengming Ding, and Zhihui Wang. Rethink maximum mean discrepancy for domain adaptation, 2020. URL aattps:/arxivv. org/ abs 00689
[67] Kun Zhang, Bernhard Schölkopf. Krikamol Muandet, and Zhikun Wang. Domain adaptation under target and conditional shift. In Proceedings of the 30th International Conference International Conference on Machine Learning Volume 28, ICML' 13, page 11--81--II-827 JMLR.org, 2013.
[68] Xuezhi Wang and Jeff Schneider. Flexible transfer learning under support and model shift. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, ed- itors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL httpttpp://prcceedigngs.ss inerr neurips. cc/ wacc/papr__aeee files/ wwweefffleeeppppeeeeee ptt.le///ppper////11eeee ppff
[69] Remi Tachet des Combes, Han Zhao, Yu-Xiang Wang, and Geoff Gordon. Domain adaptation with conditional distribution matching and generalized label shift. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY,
USA, 2020. Curran Associates Inc. ISBN 9781713829546.
[70] Junhyunng Park and Krikamol Muandet. Regularised least-squares regresssoo with infinite- dimensional output space, 2022.
[71] Zhu Li. Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton. Optimal rates for regularized conditional mean embedding learning, 2023,
wtwp/rgg//bb//aa/aaa//////// 01711
[72] Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton. Towards optimal sobolev norm rates for the veltor-valued regularized least-squares algorithm, 2024. URL https
//arxiv.org/aat otgg////////// 2
[73] Timothy Nguyen, Zhourong Chen, and Jaehoon Lee. Dataset meta-learming from kernel ridge- regression. CORR, 0ttp/2011.00055 2020. URL httppp::/aaxxi..rrrrabb///////// 00050,
[74] Trevor Campbell and Boyan Beronov. Sparse variational inference: Bayesian coresets from scratch, 2019.
wtwpg///////...././//./ 03329
[75] Dionysis Manousakas, Zuheng Xu. Cecilia Mascolo, and Trevor Campbell. Bayesian pseudo- coresets. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 44950-149610 Curran Associates, Inc., 2020. URL URL Utt.hatpss//ppoceediins wwweedddiiiinnnnnnnsseeeeeeeeeee cc/ httpcc/pppppa cttppsscccppppppppppe http:/aaaeeeeepppeeaaaaaeeeeeeee htteee/ffieeeeppppreeeeee wtt.f/eee//appr//2////eeee bb522356662224440000000224222222
pdf
[76] Ingo Steinwart. On the influence of the kernel on the consistency of support vector machines. J. Mach. Learn. Res., 2:67-93, March 2002. ISSN 1532-4435, doi: 10. (0.11662/55224430766113333
URL URLhttts: httph::t/////o 10 ottp://....111/55534347766513533
15

---

[77] James E. Gentle. Matrix Algebra: Theory, Computations, and Applications in Statistics.
Springer Publishing Company, Incorporated, 1st edition, 2007. ISBN 0387708723.
[78]
K. B. Petersen and M. S. Pedersen. The matrix cookbook, October 2008. URL http://www2
imm imm.dtu.dda.... wttu..kkpubdbbp.pae phppp/32 Version 20081110.
[79] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Minn and
Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
[80] Damien Garreau, Wittawat Jitkrittum, and Motonobu Kanagawa. Large sample analysis of the median heuristic, 2018. URL https::/arxiv..rrgeeee..e
http//rxivvv... http//bbb11777.779999
[81] Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization, 2017. URL https://arxiv org/ abwaabssia 141./111...000 6980
[82] DeepMind, Igor Babuschkin, Kate Baumli, Alison Bell, Surya Bhupatiraju, Jake Bruce, Peter Buchlovsky, David Budden, Trevor Cai, Aidan Clark, Ivo Danihelka, Antoine Dedieu, Claudio Fantacci, Jonathan Godwin, Chris Jones, Ross Hemsley, Tom Henmigan, Matteo Hessel, Shaobo Hou, Steven Kapturowski, Thomas Keck, lurii Kemaev, Michael King, Markus Kunesch, Lena Martens, Hamza Merzic, Vladimir Mikulik, Tamara Norman, George Papamakarios, John Quan, Roman Ring, Francisco Ruiz, Alvaro Sanchez, Laurent Sartran, Rosalia Schneider, Eren Sezener, Stephen Spencer, Srivatsan Srinivasan, Miloš Stanojevié, Wojeiech Stokowiec, Luyu Wang, Guangyao Zhou, and Fabio Viola. The DeepMind JAX Ecosystem, 2020. URL http://gittub..com com google -edemmindd
[83] Yann LeCun and Corinna Cortes, Mnist handwritten digit database, 2010. URL http://yann Lecun.com wwt..comeeeecee /ttp//xdbbmm////////////////
[84] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278- 23244, 1998.
[85] F.W. Byron and R. W. Fuller. Mathematics of Classical and Quantum Physics. Number v. 1-2 in Dover books on physics and chemistry. Dover Publications, 1992. ISBN 9780486671642. URL https: //books. google. co uk/ book:booos//o//o htt//bokssiddpple 7oookss7ddppnd800211155
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our claims are backed by both theoretical and experimental evidence. Our main contributions are outlined in Section with links the relevant sections the paper. See Section B for proofs of our theoretical claims and Section C for further experimental evidence.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section 6 for a discussion of limitations. Whenever assumptions have been made, effort has been put forth to describe their strength e.g. in Section B.I complexity of our algorithms has been discussed in Section D.2
Computational
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
17

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: General assumptions are detailed in Section B. with additional assumptions
listed in the theorems/lemmas themselves. All proofs are Section B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We use publicly accessible datasets, and all details required to reproduce the experiments are included in Section C Code to reproduce the results can be found at hhtps //github. com/ coonitioonniliiiiiioiiciiicooiit tionallooooooooo dummy/ heeimm/ddumyyaoe dummy_repo with scripts to run experiments and notebook to make figures included the supplemental material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
18

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We use publicly accessible datasets, and have open-sourced our code at attpp://githin: com/ conditionaldummy ddumy_rrepp
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cct
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In Section C we reproduce all necessary details of our experiments. All details are also further included in the experiment scripts provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: percentiles.
Where appropriate, we have included error bars in the form of 25th and th
Guidelines:
19

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative етror rates).
If error bars are reported in tables or plots. The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have included the hardware and software specifications used to conduct our experiments in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We followed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [No]
20

---

Justification: Our work is not tied to any particular applications, and is not related to any private or personal data, and there no explicit negative social impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Answer: [No]
Justification: The work is not tied to any particular applications, and so we not foresee any high risk for misuse of this work
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The creators of any of the assets used in this paper, such as code and data, have been appropriately recognised, with licenses and terms of use clearly mentioned and respected.
Guidelines:
The answer NA means that the paper does not existing assets.
21

---

The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the datasets..paerssttt paperswi thcode. com/datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
22

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question:
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs
used in the development of this work.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.LM policy for what should or should not be described.
23

---

Appendix
k(z, 2,) Ex-Px [k(2,x)) Table of Contents
A Further Discussion
24
A. Related Work
24
Future Work
27
B
Proofs
28
B.
Technical Assumptions
28
8.2
Equivalence of Optimising the JMMD and Joint Kemel Herding
28
B.3
Derivation JKH Objective and Gradients
B.4
Derivation of JKIP Objective and Gradients
30
B.5
Proof of Theorem 4.1
33
B.6
Proof of Lemma 4.3
34
8.7
Proof Corollary
36
B
Proof Lemma
36
B,9
Derivation of ACKH Objective and Gradients
37
B 8.10
Derivation of ACKIP Objective and Gradients
41
B.11
Accelerating Objective Computation for Discrete Conditional Distributions
44
Experiment Details
45
Additional Figures and Experiments
46
Flexibility of AMCMD versus KCD/AMMD
64
C.3
largeting Family of Conditional Distributions Exactly
65
Algorithm Details
D Pseudocode
70
D.2 Complexity Analysis
75
A
Further Discussion
In this section we include further discussions and conclusions that could not fit in the main body, including related work, applications, limitations and future work.
A.1
Related Work
A.1.1
Standard Distribution Compression
As noted in the introduction, numerous distribution compression methods exist which target the distribution of unlabelled data. Most of these kernel-based methods that target the MMD, with one notable exception (Support Points), which can actually be shown to be equivalent to kernel-based method for specific choice of kernel. To the best of our knowledge, no existing method performs joint or conditional distribution compression as defined in this work. We now briefly summarise the existing approaches.
Kernel Herding 3 41 constructs a compressed set by greedily minimising the MMD, optimising point at time. Let X = 11, F2,..... xr,] Rd be i.i.d. sample from the target distribution Px. and let Z :
|2|, 2 ... =m] C pd denote the current compressed set. At each iteration, the next point is chosen by solving
m
1m++1 arg min SERd
m + 1 j=1

---

after which the compressed set is updated to Z := [2 22..... 2m, mm+1] and the process is repeated. This greedy strategy has the advantage of focusing computational effort on optimising one new point at time while leaving previously selected points fixed. However, it may yield suboptimal solutions, as earlier selections are never revisited or refined. This optimisation approach is used to target the joint distribution in Joint Kernel Herding, and the conditional distribution in Average Conditional Kernel Herding.
Gradient Flow M methods address the problem of distribution compression by solving discretised Wasserstein gradient flow of the MMD. In practice, this corresponds to performing gradient descent on all points in the compressed set simultancously, i... solving
arg min ZCR
k(z,, 2,)
Ex-Fx [k( x)]
m
2,=1
Under certain technical convexity assumptions on the objective M.. this method can be shown to converge to the global optimum; in practice, however, one should only expect to obtain a locally optimal solution. We take this optimisation approach target the joint distribution Joint Kernel Inducing Points, and the conditional distribution in Average Conditional Kernel Inducing Points.
Kernel Thinning [2 constructs compressed set that is proper subset of the original dataset, i.e., all points in the compressed set are drawn directly from the input data. This restriction stems from the method's 'sse original motivation of thinning the output of Markov Chain Monte Carlo (MCMC) methods, where subsampling is commonly referred to as standard thinning. Kernel thinning proceeds via two-stage procedure targeting the MMD. First, the input dataset is probabilistically split into 2 MMD-balanced candidate sets, each of size [n/2nM| J. discarding the remaining n 2nm [n/2mm] points n is not evenly divisible. Second, the best candidate set from this partitioning is selected, and then greedily refined by iteratively replacing points with others from the original dataset whenever doing so improves the MMD. This construction enables the derivation of convergence rates that are state of the art in the literature, however practically it has the significant disadvantage of throwing away potentially significant amounts of information in the n 2 nn/2'' points.
Support Points [0] is a method for constructing compressed sets that takes a similar optimisation- based approach to Gradient Flow methods, but targets the Energy Distance (ED) rather than the MMD. The ED between distributions Fx and Qx is defined as
ED(Px, Qx) == 2 Ellaa - bl|2] EII a'll2] - E| bl112],
where a, a' ~ Px and b, b' ~ Qx. Much like the MMD, the energy distance is zero if and only if
Fx = Qx [10] Theorem 1]. Although Support Points not initially expressed in kernel form, the
energy distance is in fact equivalent to the MMD for a particular choice of negative-defintee kernel 48
A.1.2 Dataset Distillation
Dataset distillation produces a compressed set which attempts to replicate the performance of the orig- inal data on a downstream task, most typically image classification 44)] However, these algorithms are model-dependent and preserve task-specific performance. In contrast, distribution compression model-agnostic: distributional diserepancy is targeted, independent of any downstream model. The aim is not to preserve performance on particular model, but rather to preserve the distribu- tion itself under compression. Therefore, the approaches introduced in this work are task-agnostic: the compressed set could be reused across diverse downstream applications, as discussed in the introduction.
A.1.3 Maximum Mean Discrepancies for Conditional Distributions
The Maximum Mean Discrepancy (MMD) was introduced as a metric on the space of distributions Fx and has become widely used in machine learning 2 More recently. there has been growing interest in developing MMD-like discrepancy measures for conditional distributions [18 19 42 50 One such discrepancy:
ExnsP [|lиУ|== -M [
was introduced as the Kernel Conditional Discrepancy (KCD) by 119 to measure conditional distributional treatment effects. Independently, 42 proposed the same object under the name
25

---

Average Maximum Mean Discrepancy (AMMD) in the context of generative modelling. They are limited to cases the outer expectation must be taken with respect to the distribution of the shared conditioning variable Px- In contrast, we introduce the Average Maximum Conditional Mean Discrepancy (AMCMD):
V BBwFxx ||la|x=== MY
which allows the outer expectation to taken with respect to a distinct distribution over the conditioning variable. This generalisation extends the applicability of AMCMD beyond KCD and AMMD while still recovering their results when setting X X' X*. Moreover, we show that the AMCMD satisfies the identity of indiscernibles, and the triangle inequality under the conditions of Theorem 4.1, therefore satisfying the properties of a proper metric over the space of conditional distributions. Furthermore, unlike in [42]. we show that the AMCMD can be consistently estimated using i.i.d. samples from the joint distribution, rather than requiring access to i.i.d. features æ; with conditionally independent responses yi,j at each Z; highly restrictive assumption. We derive closed-for forrfffmmmmmm estimator for the AMCMD that is similar in form to the one proposed for KCD by [19], and show consistency of the estimate in the case that X X' X (Corollary 4.4 which the case under which our compression algorithms lie.
The Conditional Maximum Mean Discrepancy (CMMD) (50p defined as
CMMD(Py) Py-jx := ||wx| - PY (lss(H..H.))
measures the for use in moment-matching networks, the CMMD has since been applied to domains such as domain adaptation (51) and stochastic differential equations (SDEs) [52] However, as noted in [42] 18], the strong assumptions required to ensure that JY| and JYLIX exist Hilhert-Schmidt operators imply that CMMD may not even be well-defined at the population level in many settings, unlike the AMCMD.
norm of the operator difference Jylx - Prijx. Originally developed
A.1.4 Accelerating the Kernel Conditional Mean Embedding
The most closely related work is that of [53] which leverages the equivalence between the operator- theoretic estimate of the KCME and the solution to vector-valued kernel ridge regression problem. They develop an operator-valued stochastic gradient descent algorithm to learn the KCME operator from streaming data. While both our approach and theirs utilise gradient- based methods, our work is fundamentally different. Instead of learning the operator, we learn the compressed set itself via gradi- ent descent. Moreover, by identifying an MMD-based objective function, we establish connections with the distribution compression literature. This shift in perspective leads to significantly different formulation and set of theoretical insights.
Beyond this, other approaches exist that are less similar. Some methods aim to speed evaluation of the trained KCME at arbitrary input, rather than the training process itself: (30] and [54] use
LASSO regression to construct sparse KCME estimates for efficient repeated queries. Working in
Bayesian Optimisation, (25 introduce a greedy algorithm that sequentially optimises the conditional
expectation of a fixed function f E Hd using the KCME. Meanwhile, [55] apply sketching techniques (6) to approximate the KCME, however they not deliver a compressed set. Finally, (57) propose decentralised approach where a network of agents collaboratively approximates the KCME by optimising sparse covariance operators and exchanging them across the network.
In contrast to these methods, by framing the problem through an MMD-based objective function and directly optimising the compressed set, we introduce new perspective that enables both theoretical advancements and practical improvements in scalable conditional distribution compression.
A.1.5 Supervised Kernel Thinning
In [58, the authors apply the method of Kernel Thinning [2 in order to accelerate the training of two non non-paraettric regression models: Nadaraya-Watsor Watson (NW) kernel regression, and kernel ridge regression (KRR). That is, given a labelled dataset ((æ,, yi ) x E Rd y E R. they construct a compressed set with Kernel Thinning, using specialised input kernel, and then derive hewe--thn-iid-sussaaapee bounds on the MSE achieved by the model trained with the compressed set.
26

---

More specifically, they use
kyw ((x, y). (a'.y)) == k(xx,') + k(x x') (v, 00)
for the construction of the compressed set targeting the Nadaraya- Watson model, and
kKRR((æ, v), (ar', )))) ((xx + k(x,, (y. y²)
for the construction of the compressed set targeting the kernel ridge regression model. For NW regression the feature kernel k can be infinite dimensional, and their results still hold, however for KRR, their better-than-iig bounds hold only for finite dimensional feature kernels k.
Very importantly, they make no claims about compression of the joint or conditional distribution, and indeed it is straightforward to see that kxw and kx na are not characteristic, as the linear kernel Iyy v/) := (y, y applied in both knw and ki na is not characteristic, and can recover changes only in the first moment between distributions.
A.2 Future Work
Distribution Shift:
The closely related fields of Covariate Shift [59]. Distribution Shift [60], Transfer Learning [61. and Domain Adaptation [62] have been the focus of significant research in recent years. Notably, the MMD has become widely used across these areas, as evidenced by works such as 15 666. among others. In this context, the AMCMD metric introduced in this work has natural applications, e-g- in covariate shift scenarios, as the choice of the distribution used for the outer expectation, denoted by Px-, can differ from the distributions from which the observed features arise, Fx and P xz Furthermore, the AMCMD especially relevant when one encounters Conditional Shift 67 66769, 69], where the conditional distribution of the data changes across domains.
Two-Sample Testing: The MMD originally introduced is, for determining whether two datasets are drawn from the same underlying distribution (2. that work, the authors propose an MMD-based hypothesis test and analyse its statistical properties. would be natural to undertake a similar investigation for the AMCMD, and additionally to study how conditional distribution compression affects the resulting test.
metric for two-sample testing that
Estimator Consistency: The consistency of the AMCMD estimator established via Corollary 4.4. which follows from Theorem 4.5 of [19] the special case where X * X' * X This setting aligns with our application of the AMCMD, as it corresponds to the regime in which our compression algorithms operate. However, it would be interesting extend the consistency result to the most general case, where X * X' + X". Moreover, a promising direction for future work is to characterise the conditions under which convergence rates be guaranteed. This includes both the well-specified case, where fyjx E Hr [88 19 77), and the more general misspecified setting, where JY|X is not assumed to lie in Hr 71
72
Differential Privacy: In the work of 73 an optimisation procedure similar to that used in JKIP/ACKIP is used to compress dataset for training Kernel Ridge Regression model. No- tably, they demonstrate that test performance remains strong even with significant corruption of the compressed set, suggesting potential applications in privacy preservation. In the context of Bayesian Coresets (74.. 75 introduced the concept of pseudocoresets, where they apply stochastic gradient descent to optimise compressed set targeting a Bayesian posterior, and further establish differential privacy guarantees by corrupting gradients. It would be interesting to investigate the impac of corruption on the performance of compressed sets in setting and derive corresponding differential privacy guarantees.
Global Conditional Distribution Compression: The compressed sets generated by ACKH and ACKIP focus on compressing the conditional distribution in regions where Px has high density, due to the use of the AMCMD objective function. An interesting direction would be to develop methods that provide a more uniform weighting across the entire conditioning space, ensuring balanced compression regardless of feature density variations. This may be particularly valuable for cases where data observed at the tails of the feature distribution are especially important e.g. in health related scenarios.
Alternative Optimisation Strategies: Further exploration of alternative optimisation strategies targeting the AMCMD could also be valuable. Potential approaches include algorithms inspired by Kernel Thinning, second-order methods such as Newton or Quasi-Newton techniques, and metaheuristic strategies like simulated annealing for identifying global optima.
27

---

Real-world Applications: Finally, it would be interesting to see how the compressed sets generated by ACKIP perform when used estimate KCME applied in the important real-world downstream tasks 17 32 beyond multi-class classification 33 which we have explored in this work.
B Proofs
In this section, we provide technical proofs for the results in the main paper, and rigorously describe and discuss the assumptions that we adopt throughout the paper.
B.1 Technical Assumptions
The assumptions that we work under are laid out in this section, alongside commentary on their restrictiveness.
In order to guarantee the existence of the kernel conditional mean embedding Jyj := Eppix [((Y,)) .)] require that : y R is measurable and Epy [vI(Y, /I(Y,Y) Y)] < xo. However, to ensure that My|x is an element of the space of equivalence classes of measurable functions L2 H4), we actually require that Ep, [(Y, Y)] de 18) This fact is needed for the proof of Theorem 4.1 hence we make this slightly stronger integrability assumption.
18
For there to exist deterministic function Fyix X' - H/ such that JY| = Fylx o X, we require that H. is separable, which is not a restrictive assumption, and is guaranteed if the kernel x x X' + R is continuous [18). or if Hi is finite dimensional, c.g. when / is the indicator kernel defined on a subset of the natural numbers. Recall that in the main body of this work, and for the remainder of this section, when we refer to μY|x: we mean Fyjx-
In various theorems throughout this section will make assumptions that kernels are bounded, characteristic or universal. Assuming a kernel k defined on X' is
1. bounded ensures that there exists some constant B such that sup k(æ, x) S B. This assumption is trivially satisfied for many commonly used kernels such as the Gaussian, Laplacian and indicator kernels.
2. characteristic ensures that the corresponding kernel mean embedding μx injective, and hence the corresponding MMD(Px Px.) is a proper metric. On Rd, the Gaussian, Laplacian, B-spline, inverse multi-quadratics, and the Matérn class of kernels can be shown to be characteristic [40] and on No == {0. 10.1.... C}} the indicator kernel is characteristic 133 Note that & @ (X x y) (X' )) + E characteristic in the case that & and I are continuous, bounded and translation-in iiniarinnnniiiittt kernels (e.g. the Gaussian, Matérn and Laplace kernels) (Theorem (4))
3. universal ensures is continuous and that the RKHS H4 is dense on the space of continuous functions C(X)). That is, for every function f C(X), and every e >> O, there exists function g E H/ such that |lf gll>o S [76]. This assumption satisfied for many common kernel functions, e.g. the Gaussian of the Laplacian [8]
B.2 Equivalence of Optimising the JMMD and Joint Kernel Herding
In this subsection, in order guarantee the existence of the joint kernel mean embedding μx.yy He & H4, we must assume that k X' X + R is measurable with Er [k(X, < oc, and that measurable with Ep, [(Y, Y)] < co. We also reiterate the assumption from the main body that [|ı( (,, = R for all æ E X' and E V, where R is constant. This of course implies that
1:3 1:y' x y -
[k(x,))((,, (lce))))( (k(x,))((y k(x (x.,))(y )) (k(#, ) kzx )) (1(y, 1), (y.
k(x, (g 3) =²² for all æ E X and y E y.
Now, assuming we are the (m + 1)th iteration of Joint Kernel Herding algorithm, having already constructed compressed set of size m, C { ;; ",)) the next pair is chosen the solution
28

---

to the optimisation problem
m Σ
arg min (m. (m.y)eXxx + k( k(, 2,)((,)) (...))))) ;,) -Bex [k(x, Y)]
We now show that these updates greedily optimise the JMMD(Px.. x.I, (x.x) between the joint kernel mean embedding estimated with the compressed set, and the true joint kernel mean embedding. Adding (z, y) to the compressed C'", we compute the JMMD x,y, ,,,,,,,P,))))))) Px,r) as
|
2
Σ k ()..)) + k(x,, ((,,))
1XYYY +
HL
m
2 PX,Y: m + 1
Σ k( (. + k(x,, My..))
Ho
+ (m 1)2
k(āj, )( k(x,)) ((y.))
+ M(x, ((..)
Bi (a wxxPx. (=((@t='') + E ( 1k(, x ('))(())))))
+
i, Uz) + x) +
k(x, ãz M[. ;z) + k(0, ())( y
(m 1)2
1==1
j=1
2 E E [k(x, ((ly.'))l (m - 1)2
2
m
Ci C2 C2+ 9
k( ã., N ú,).
m +++1
where (a) follows from expanding the squared norm; (b) follows from linearity of inner prod- ucts and the definition of the joint kemel mean embedding: and (c) follows from setting G == (px,Y, (x,Y) Ho C2 == m+1 Σx= (/,'.x')~x..v (k(
C33
- ( Ø,). and C₁ (m+ty k(æ, a))( y), where we have assumed C₃ is con- optimising with respect to (ær, y), can ignore those invariant terms, and
stant. Now, solve the optimisation problem
arg min (a. (xx (m
Σ k( (ln. (zy.0)
2
B a -xx, [Me( x (y, v'))
1)2
which the change in JMMD(Pxxy Px,y) from adding the point (æ, y) to the compressed set. Note that this is exactly equivalent to solving the optimisation problem
m M
arg min (a (xx) m + k(x 2,), 91)) Eex,
which is precisely the update used in Joint Kernel Herding.
Remark B. In general, one can not usually evaluate the joint expectation in (2). and hence this is estimated using the samples from D, corresponding to optimising the JMMD(P (AMD(Pxxyy. Pxx.)
29

---

B.3
Derivation of JKH Objective and Gradients
We denote Cm
Rd
R
P to be the estimate of the objective in using the entire dataset D,
then
C (
m
k(x, F (3, 01))
1 Σ
kax (,,,
71
1
m + K (x)) Em(()) Kn (xx) "n((y)
(12)
n
where Km (x) [k 31). k( x Tmm) T and (x) (y) [y, .1),..... MVy Dm )) and L,, == (1(y. v1), Myyyn))]
[k(2 21), 21)........ k( x,))"
We solve the optimisation problem (2) using gradient descent, henee we need to derive gradients of 12 with respect to both and y. It is straightforward to see that
1
m (z,
V km (y) vv)k( (y)
(13)
+
and
K km(x) T V (ymmm()) (x(x)) ( (y)
(14)
+
n
where we have defined
V K (z) == Vol(2, Vak(o, 2m))
E ERppp
V K, (x) V x1
vak(o, xmn)
E ERax
V L m (y) == V 91 (y Fmm)l )1
E Rmxp
V (,) = VV 9n) Vyl(y. yn)]
R=xp,
Hence, it is easy to see that the gradient can be computed with 0(m + n) time and storage complexity.
B.4 Derivation of JKIP Objective and Gradients
Before state and prove our lemma, we first recall some properties of tensor calculus.
B.4.1 Tensor Calculus
Let F Rm + gmxm be a matrix- valued function taking matrix-valle valued inputs with
k((1,
k(x11, xmm)
K(X)=
E Rmmx
k( x1) k( xm. xm)
E Ruuxd az E Rd for where hs Rd x Rd + RR will be some kemel, and X [z]...., 2m]
i I....,,. m. Then, we have
X Xx))a = K(r,, m3)) E TR.d i, 1,...,,,
such that Vx KXX, (X Rmxmxmxd, i.e. fourth-order tensor. With some abuse of notation, we reproduce the usual derivative identities below, for a more in-depth review see, for example, [77
Trace Rule: Given some matrix A E mm we have
V (TT(K(())) (r (rVVK((XAA) mxd
(15)
which establishes the linearity of the gradient operator with respect to the trace. Note that the trace on the RHS is understood here to be partial trace over the last two dimensions of the fourth-order tensor, i.e.
m
TT [VVx((X) Σ
[ Ass E Rdd 1=,,..,
(16)
J==
30

---

Inverse Rule: We also have
Vx
R
(17)
assuming ((X) -1 E ER" mm exists, where
[ Vijpp
Σ
[(X)
V K
stpg
s,t=1
Product Rule: Given a second function L Rmxd 1: Fd X R I. then we have
Rm xm defined similarly K with kernel
V Vx (x(K(x)((X)
+ X E R.xmxmxx
(18)
where we have
V (x(((X) (ippg
kipp
Σ
[Vx((X) lispo ((())ss + [K(X]]s
VXL(X))
B.4.2
Statement and Proof of Lemma
Letting CP mRmxdd x RR + R the estimate of the objective in using the entire dataset D then we have
((X
k( 3z Mi.. Bj)
2
Σ
k( F. M(.. vj)
m xy=1
1
2 Tr K xxxxLx
Tr K x
m
mm
where [Kx]]; k(ä,, k2). [K x x lig k(ū,, Zg). LLvvl = ((g Wj), and [Lyyli 13 vo), ) for i = 1,..., m and g = ,.
Note that optimising this objective with respect to the compressed set (X Y) is equivalent to optimising the JMMD between yx,y and Px,y, that is, the empirical joint distributions of the full dataset and the compressed C respectively:
JMMD2 (Px.y.xx.)
-1xx, iuxx 11
2 xHY +
(ixXY,PxYY)) + CC
Lemma B.2. We compute the gradients of the objective function L R.mxd x RRx - R as
- Tr x x
2 Tr (V
V x (X,
(19)
112
1
2 2nr
(8,
//
Tr
K
V V
K x V v
(20)
mi
where
V x E R.xmxmxd with
V V K x
= Va,k(i; k;)) E Rd,
179
x E mmxxxmxd with
V x K Kx
Va,k(ā, m.)) E Rd.
bj
V E mxxxxxx with
V y
Vg, (i 3 RR.
154
V E
E R.xnxmxp with
V
= Vg, V yj) E RP,
with Omn + m²) time and storage complexity, i.e. linear with respect to the size of the full dataset
D.
31

---

Proof: We have
C (² = m
Tr
mn (x)
Tr [ (KxxLxx).
Applying rules
(5 and
18 it straightforward see that
2 Tr (V k xxxxxx(xxx)
x
x
Tr
xxxxx)x1,xx)
m
mn
and
_ Tr V
2 Tr (Kxx V vylr,
Vy (x,
m²
mn
Now, in order to show that these gradients be computed with O(mn + m²) time and storage complexity, the critical observation is that the majority of the elements of these fourth-order tensors will be equal to zero, i.e.
V K x
x
=
Va, (e, .z, 0 when i i and j 4.
ij9
K
xxX
= Va, ka, = when i +
159
and
V y L.v
=
V ú. (Ú: Dj) = 0 when i + and j q.
639
V Lr
= V 9, (gi. yy) = when *
Then, by using the identity in (6). we have that,
Tr ( (V
x K x ijor
[4r,8] gr
1=1
m
m
x K
x
igar
5=l
L
(21)
iggr
for q = 1........... m and 1...., , d. and where (a) follows trivially from the symmetry of the kernel functions ((.,-) and k(-,-) Hence, here, the only terms we have to compute and store are
K 2., E Rdd i = l...., m, q 1,...,
and Ly y mmm which can be accomplished with cost O(m²) in both storage and time, ignoring any dependence on the dimension of the feature space d. A very similar derivation holds for the term
Tr [ V y L.
Now, tackling the cross term, we can use (16) to get that
Tr V K xx
=
x x,x
K
[ x
ijor
im 1=
= Σ j=1
V
x
(22)
qior
jq
with 1..., m and 1,..., d. Hence the only terms we must compute and store are
hi 22)) E Rdd g q= g.....,m m. j 1...... n,
32

---

and Ly I which can be accomplished with cost (nm) in both storage and time, ignoring any dependence on the dimension of the feature space d. Again, a very similar derivation holds for the term
v
Hence, the final computation and storage cost of computing the gradients Onm + m²), i.e. linear in the size of the target dataset D.
Remark B.3. Above we have derived analytical gradients of the objective function, and shown they can be computed in linear time. In practice computes the gradients using JAX's [79] auto- differentiation capabilities. The authors observed minimal slowdown from using nuto-differemtiation.
B.5 Proof of Theorem 4.1
Theorem B.4. Suppose that y y + R is a characteristic kernel, that P Px, Px's and Px are absolutely continuous with respect each other, and that PP X) and P-- X') admit regular versions. Then, AMCMD [Px Pxx,Pr Pr = 0 if and only if. for almost all a E X wrt Px-, Py|x== = P (B)for for all BES EV
Moreover, assuming the Radon-Nikuud Nikodym derivatives gle inequality is satisfied, i.e. AMCMD AMCMD Pyx
xx &xx &x are bounded, then the trian- d' dFx' d'x
[P [xx, Pyix, Pym[x"] S AMCMD [Pxx, TPxx,Pyixe PY|x, Prqx]] +
Proof:
It is clear that
AMCMD PXxx,Prxx Prix] = v RRwEx [llxa|== - My x== m.
non-negative and symmetric in Pyjx and Py
We first prove the equivalence result:
) Assume that AMCMD Pylx, == ExwPxx [|lx||== PY [.
O This implies that PY|X== = PY"X'== almost everywhere æ wrt Pxx. Now, by the fact that Pxx- and Px (or Pxt) are absolutely continuous with respect to each other, we also have that HY|X== = HY'X'= almost everywhere wrt Px (or Pxx). Hence, we must have 0 almost everywhere E E X wrt Fx (or Px.). Thus, by Theorem 2.1 have that for almost all æ E X' wrt Px (or Ix)), Prix== (B) Pr for all E y. However, again by absolute continuity of measures, this is equivalent to stating that for almost all x E X' wrt Prlx, (B) = Py (B) for all B E v
MCMD (Pyix=,IPypx=> == -ylx= MY'Ix'=
(=) Assume that for almost all x E X wrt Px-, Prix== Pr (B) for all B E V. Then, by the fact that Px- and Px (or Ix)) are absolutely continuous with respect to each other. and Theorem 2. we have that MCMD Pyixx,,Prxxxe
== || MY H: 0 almost everywhere wrt Px (or Px)). This implies that By x= =y almost every- where x E X wrt Fx' (or Px'), and by absolutely continuity, Px- also. Hence, we must have AMCMD PX P PyIx, Py-p = EEawXx [ - = PH
0.
Finally, show the triangle inequality, that is, given additional random variables X" : Ω X, Y" + Y, with conditional distribution PYn"x" and KCME py*px", we show (suppressing the first argument Px-)
AMCMD [ PY < AMCMD Fyjx,Pryiie + AMCMD
33

---

Firstly, denote (2 x(: Hi) to be the Banach space of (equivalence classes of) measurable functions f X + Hz such that || l| is isPxx iiiiintege with norm defined by
( (1f((z)) dP dlxx
f
Now, it is shown in [18], that дajx belongs to (2X Ix: 74), where we stress that the measure is Px, not Px-. They arrive at this conclusion by the measurability of μYlx, and by noting that
/ dP (x)
Erx
[(X,)))
GIA
Epx
EPvix [[((Y,-)
Ery [II((,-)) ((IY ). Epy [(YYY)] < 00
where (a) follows by the definition of the KCME; (b) follows by the Generalised Conditional Jensen's 's Inequality (Theorem A.2 [18); and (c) by the tower property, the reproducing property, and by our integrability assumption.
Therefore, by further assuming that the Radon-Nikodym derivative dFx is bounded, i.e. there exists dP'x
some constant M > 0 such that d''x dFx (x) & M for all a E X, we have
S |layxx=mll dFx dPx. (x) Exxx [[l ((Y,)) [] [1
M Epx Bpix [I(Y, .)] [1 < 30
where (a) follows directly from the boundedness condition. Thus, it is now clear that Jylx E I (2,, Px: Hi). Hence, assuming that d'xx and dFx are also bounded, the functions f.g: X x' xt"
Hi defined by
[(x) == JY|X=> - X g(x)) = PY'X=== MY"|"==
belong to L2XX, H.). the Minkowski inequality, i.e.
The triangle inequality then follows by straightforward application of
|| + gll, S [|f + llll
for the special case where = 2.
Remark B.5. Assuming the Radon-Nikodym derivatives arguments above it is clear that
dpx- and dPx- are bounded, by the dPx dpx
AMCMD [Pxx, PYIx, Prixx] == = BENTTx [llx||== - MY x== [,,
=Ilx|x Py (Xx
that is, the AMCMD can understood as the norm of difference of py and pyqx in L2 H4) space.
B.6 Proof of Lemma
Lemma B.6.
AMCMD Px-xPyix,PPs
+ IT W
where have defined Wx (Kxix + 1m with [Kx = A(/), Wxx (Kx'x + Am 1)- with [Kxx]ú = k(a; R.)) xx k(x',x²),, Kx-x = KT K
LyYlis == 1(,, ),), LLY == 1(y, H;), and LLx. 12,1
34

---

Proof: We have defined
AMCMD
[Px-, Pr = q
|| A - -
Using equation we have
Pr|x== Σ 2z,,z;) Ampx- = Σ ka, W.,
then we can expand the MCMD as
||xxx== axixall = ( (x (23)
Now,
(Drxx=an xx
k(x, x. W.ylly, )
Σ 8,1=1
k(x xl ".),
k( x; Wij (1y), )) Uv' )), k(æ, ((o. w')
k(x, n. W, uf (ar a'
k(x, W
where (a) follows from the linearity of inner products: (b) follows from the reproducing property on Hr; and (c) follows from symmetry of the kernel k(,, :). Therefore,
Σ k( x, (/)
- (Kx.x W W W Xxx:
where the second line follows from Tr(AB) Ei arzbi. Here we have defined [K x x == a()) Wxx (Kxx A1) LyY [1 USleg Wx.x (Kx-x AI) and [Kx'x-1; x3),
Noting that the derivation of the first and third term of 23 follow very similarly, we can easily see that
1
AMCMD Prix, Py-px:]
|y|x==:
9 i=1
Tr (Kx-
2
+
35

---

B.7 Proof of Corollary 4.4
To state Corollary 4.4 in full context, we first introduce some additional definitions and notation. Let L(HH) denote the space of bounded linear operators from Hi to itself. An operator-valued kernel I; X' x X' + L(H,) induces a vector-valued reproducing kernel Hilbert space (vvRKHS), denoted Hr. which consists of functions f X Hi (see (38] for further details). The vvRKHS Hr is Co Hr S Co Hı), the space of continuous functions from X' to H, that vanish at infinity. Moreover, the kernel I' is called Co-universal if it is Co and Hp is dense (2 Px; H2) for any probability measure Pxx on X. Denoting the identity operator on H4 by Ine it is shown in [38] that the kernel T(x,=') = kxx, x ITn, Cy-uniivrsal whenever is universal scalar kernel, such as the Gaussian or Laplacian kernel. Hence, in the statement of Corollary B.7 the assumption that k(.,,) .) is universal implies that Co-universal, with Hr as described above.
Note that the specific choice of kernel [(x, = k(r, ('r,,')IH, leads to the form of the KCME estimator given in equation (I) [19]. which we adopt this work. More generally, the corollary could be stated under the assumption that Hpp is induced by an arbitrary Co-universal operator-valued kernel I, thereby removing the requirement that be universal-followiii
the more general formulation in Theorem 4.5 of [9]. However, as stated, this would yield a potentially different form of the KCME estimator than the one used in (T.
Corollary B.7. Assume that k(.,-) and .) are bounded, k(.,-) -) is universal, and let the regularisa- tion parameters An and Am decay at slower rates than On -1/3) and O (m22) respectively, Then, AMCMD Px. Pyjx 3, AMCMD [Px, Pr,x py as n. m,m,g 9 +
Proof: Given sets of i.id. samples {x:)%=1 ~ Px, M == {(x, y ~ Px,y', and N == {(x;, y:)) Fx,y, the estimate of the AMCMD x, Py x [Pxp) defined as
9
AMCMD Pyx, =
My
Ryix==. - - Hi
with population counterpart
AMCMD [Txx, Pypx: Py1x]
Bex [|ll|x==:
-y|x===: Ht
The assumptions in Corollary B.7 satisfy the assumptions of Theorem 4.5 [9), which states that
M YI==z PY
2
B
Exx
[|laix
2 [H.
Hi
Now, it is enough to note that convergence in probability is conserved under continuous mappings, i.e.
A, 2 A co implies VA, 2 VĀ сo by the continuity of the square root function on [0, oo) for non-negative random variables A, A,, Hence, our result follows.
B.8 Proof of Lemma
Lemma B.S. Let h X Hi be a vector-valued function, then
Exxrx [HYIX=a, M(x)) Hi B( (x))
Proof: We apply the definition of the KCME, then the tower rule to see that
ExpPx [MYIX== M(x)) Hi = Em-Tx [By- (v))
B(a,y))xxx, [1(x)
36

---

B.9 Derivation of ACKH Objective and Gradients
In ACKH, assuming we are at the m iteration, having already constructed a compressed set of size m 1, Cm == {(z ú;) دー) and let Cm Cm U (æ, y), then we solve the optimisation problem
j arg min Ex' z.y
|Y|X=0"
(UYINE 2
)mll
(24)
Hi.
via gradient descent. Letting Pm Rdd x TRP + R be the estimate of the objective function in computed using the entire dataset { (r y: { i.e.
(4
(x y) = P
2
cm Py|x= (4:)
Phi iml
then have the following lemma:
Lemma B.9. We have
1 Gi (2. y)
My
m
X
2
2
Σ
My x=x (yii
cm
n
H1
n
- ( (m)
Tr
where we let
σ1)
k(x1 3m-1)
k( x))
Km (m)x)=
@Ruxm
k( Ø1)
k(@n, Tm-
k( x))
1(H1, 91)
1811, 8m-1)
1(H1,8)
E Runm
I(yn, 91)
(yyn, 1m
1(ynn y)
k(ā1,, Z21)
k(ā1,, 1m)
k( x))
K (x))
R m
1c k(#m-1, .1) koxx, Ø1)
k(ām xm
k k(@m-1,8 1. k(x,, x))
k(x, 1m
1( W1)
(( 9m-1)
1(81.8) y)
im)(y)=
E mmmm
1(0m-1, 91) 1gy. v1)
1( 1, 1m-1) I(y, 9m-1)
1( 1( y) 1(.. y)
and (x) (K (2:) Am E mmxm Moreover, G (x,, y) can be computed with time complexity Ommn m²) and storage complexity of O(mn + m
37

---

Proof: In order to reduce the notational burden, we write [m(x))]s Way. and (a, y) = (zmm Gm) then, using the estimate of the KCME from we have
2
I (ām: mm) =
x (31)
PYx==
H:
1( kāt, Fr),
Σ
Bp) pa (ār
(2. any)
p.4=1
Hi
m
my ÿt) W (1),
71
k(z,, 3 W 3p k(,
(b)
KJP..q=
(y., ú.) W.)
Tr Km (=))) (x) (w) m (x) Km (z)) () - 2Tr
(Im())) - m (xx) Km (m))) (m)
where (a) follows from inserting the estimate of the KCME and the definition of the norm; (b) follows from the reproducing property and the symmetry of the kernels; and (c) follows from the fact that Tr(AB)- Eij=i ajzby for symmetric A, B E _
The storage complexity of O(mn + m²) comes from the fact we have to store
(y) Ki (z)), (xx) E Rmxx and (x), (m)(y) E Rmmx..
The computational complexity of O(m2n + m²) arises from solving the linear system, A(Km (x) + AI) = (x) for A 2xm
which dominates the O(m2n) cost of the singular remaining matrix multiplication, and the O(m² + mn) cost of taking Hadamard products required compute the traces.
We now derive the gradients Gh and show that they are cheap to compute and store. Note that the derivative identities used in this section are similar to those in Section B.4.1 except for third-order tensors, as we deal with derivatives of -valued functions with respect to vectors.
Lemma B.10. We compute the gradients of the objective function Gh Rd x I² - RR as
( (x) (m)) V D (ar, y) Tr (m]()))
(25)
2 rr V L (v) (x))))))))
2 Tr V Km (x) (x) (x)
(x. y)
(26)
20
n1
2 Tr (m)
71
2
+ Tr ( (Ln
n
2
- Tr (Lm W (x) (x)
Where in order to reduce notational burden, we write (x., y) (im, Um). then we have
V Km (mm) E mmxxxd with V a' Km (ē bs = Van k(ē,, B, iinR
V a. Km (m))
E Raxmxd with
V a.m Km (#
}}
= V k(x;, xz)) E dR.d
Um K (im) E mxxxd with
V Vim Iim (m))
= Vin (i 95) E RP
ij
Um Lm (mm)
xxx with
Um Im (8
= Vgn. Uyy 9,) E R
38

---

with ((m2n + m²) time and Omn + m²? storage complexity, i.e. linear with respect to the size of the full dataset D.
Proof: Firstly, by applying the trace and product rule, we can immediately see that
V V (x, y) = Tr Km ( (x) bm))) (2)) (m()))
2 Tr V (m))
n
Now, we have
1 V.Tr (ROWW
I ar, v)
(a) n
2 T ([WWW())))
+ (KKKaoWWWWWooWWaa
+ Tr (KCWaWaa
+ -T (KWW)WWIWWWW n
Tr (HW)a)(())(a))
Tr (Ig))([N[
Tr (TAKo)W()][[WWWW]))])
(c)
2 (KCa))aWWWa/
2 (Iv)Va((<<)(())
where (a) follows from the linearity of the gradient operator; (b) follows from combination of the trace and product rules; and (c) follows from the symmetry of the feature kernel k(.-)). Then, by applying the inverse rule, we have
V v (x. y)
Tr (VK(()))))WW))))
2 Tr (Lo))())//KWWW)Woo
Tr ([b))(<=\V<<<)))))
Now, establish the cost of computing this estimate, the first thing to notice is that there is significant amount of symmetry and shared computation between the terms. In particular, avoiding the gradients
V VeK(x) E mmxmxd and Ka E R paxmxd
for now, we need to compute
= ((x) E m' B: Ly) E ERm
C = (() R
39

---

then we have
2 2Tr (V (Vak(z)() - - (AVoR(())))
V V
2 Tr BV (BVR(())A) 2 n
2 (T
"Tr (VaR())CA))
(a) n
2 Tr (ve((=)AB) 2 (v=
where (a) follows from the eyclic property of the trace and the symmetry of the kernels. Now, the cost of computing A, B and C' is O(nm² + m²), and given these matrices, the cost of computing : == CA mm and E == AB E Rm is (nmm²). So, we are now in a position where we have to compute
2 Tr (V (())C)
2 TT (VaR(x)))
V
2
+ Tr (x)(
(xx)
We can reduce the cost of computing these terms by noticing that the majority of the elements of our third-order gradient tensors will be equal to zero, that is
k x)
Km (x)
E R nxxx
V ka x)
Vyl y)
V Vy)m(y))
E R2xmxp
V VI y)
k(
mmxxxdd
k( xx)
x1)
k(x,, F.
k(x,
0
1(01y)) 9)
VyLm((y)
mpmxxpp
1imm- 1, 4) 1(y. y)
[ly 9
1(y 9m-1)
Hence, we have
= Σ m
V K (x)) sfr Czi
1=1
(xx) imr Omi
for == I,....d.. d. Hence this term, given C, can be computed with cost O(z). We also have
m
Tr (V,K(()))
Σ
V [(x)
Djr
ijr
m
m
V K (xx)
mnrr Dim +
V [(o)
Dmn
imr
V ((x))
Djm
mjr
j=1
40

---

where the last equality follows by the symmetry of the kernels. Hence this term, given D, can be computed with cost (m). Similar derivations hold for Tr (x) B) and Tr (z)
Therefore, we have an overall storage cost of O(mn + m²), and time cost of O(m2 + m²n), i.e. linear with respect to the size n of the full dataset D.
Remark B.11. Above we have derived analytical gradients of the objective function, and shown they can be computed in linear time. In practice one computes the gradients using JAX's [79] auto- differentiation capabilities. The authors observed minimal slowdown from using auttodifferentiation.
B.10 Derivation of ACKIP Objective and Gradients
Noting that C = (X, in ACKIP we solve the optimisation problem
(X,8 MYIx=
(8,8 Prix= (v')
arg min Bx X,Y
2x w'xP
(27)
Pr.
via gradient descent. Letting JD: R x Rux -> R be the estimate of the objective function in 27 computed using the entire dataset D = { yi) > i.e.
J9
(8 -
2
,
(8,8) -
(y:)
==1
we have the following lemma: Lemma B.12. We have
J
(8.8)
12
2
Σ
(8.8) Y|x= (1))
11X==1117 Hi
t=1
1=1
- (K x x
2 (yy W Wx xxx,
2
W x L W
xx)
n1
where x == kl وe ). KK x big == k(ē; }g), / lis == l( 3,). [Lvrlg == U(). and [Wxx]e, x( = (K xx + XI) for i,j l..... m and q ... n.
Moreover, JP(X, Y) can be computed with time complexity of Om + mn + m²) and storage complexity of Omm + m²).
Proof: Using the estimate of the KCME from I and writing [ *
Way we have
2 2
JD
v|x =a;; (yi)
n1
x
=
Hi n
1(s ū.
W. 2r),
Σ
M1 Gp Wpghhprr sig)
(2) 12
p-9=1
Hi
2
Uy.. ((,
71
T
k(x,, き. , W (3
(5., 3p Wmy
(b) 71
k.j.p.q=1
2
Upp Wiyk(, xpp)
n
p=1
(K x Wxx W xxx) - 2 wxx
where (a) follows from inserting the estimate of the KCME and the definition of the norm; (b) follows from the reproducing property and the symmetry of the kernels; and (c) follows from the fact that Tr( AB) = n Dij=i asybys for symmetric A, B E 2x
41

---

The storage complexity of Omm + m²) comes from the fact we have to store
Lvv, xx Wx Wxx R and K xxx: l' R
The overall computational complexity of O(m²n + m²) arises from the cost of solving the linear system,
x(xxx + XI) = Xxx for A Ru
which dominates the Om)²n) cost of the singular remaining matrix multiplication, and the O(m² mi) cost of taking Hadamard products required to compute the traces.
We now derive the gradients of Jp, and show that they are cheap to compute and store:
Lemma B.13. We compute the gradients of the objective function Jo + Rmxd Raxd + as
2 Tr (V
V xxJo(X
x xx x w
(28)
2 Tr [K xx x (
2
+
1r x
n
2 W
n
Tr
K &
(29)
1
2
Tr (V
where
V V E Pmxmxmxd with
V x K x
= Va,k(i. kU) E Rd
119
V B.xxxmxx with
v K x. x
= Vn, (a, 23)) Rd.
V & E RRxxMMxx with
V 1 v
Vg, (ii 93) R?
139
V V E RuxXxmxp, with
V 8
= Vg, ( y₁ E RP,
and W (Kxx + XI)-1, with O'm'n + m²) time complexity and O(m + m²) storage complexity, iee. linear with respect to the size of the full dataset D.
Proof: We use the batrix-by-matrix derivative identities from Section B.4. Firstly, by applying rules (15) and (18) we can immediately see that
1 T X Wy
J (X.
Tr (VVyyyyWxxKsr
42

---

Now, we have
V Vx r)
Ir "a
2
Tr
1 -TiKkr>Wsz/<>>>/aaxxx
1 x
+
71
2 <Tr(byy ViIIyyxxWxxxxx>
n
2
Tr (L y W xx vx
2 (V x K x W W
2
Tr (K x X
71
2
Tr ( x W xxxxxxxx xx)
Tr (Lyy x xxx))
where (a) follows from the linearity of the gradient operator; (b) follows from combination of rules
15 and (8 : and (c) follows from the symmetry of the feature kerne k(,,-). Then, by applying rule
we have
J X
8
2T V xx Wxxxx>xxxwWWskK
"
2
Tr (K
xx
xx Wxr
n
2
+ Tr (Lyy W x x K
xxx)
2 Tr (Lyv W X
Now, in order to establish the cost of computing this estimate, the first thing to notice is that there is significant amount of symmetry and shared computation between the terms. In particular, avoiding the gradients
V k XX E RRxxmmxxd
V xx E
ER mxmnxmx
k xx E Rxxmxmxxd
for now, we need compute
A: = K Kxx W
WXX XX E nnx B= W XX E mmm
C Wxx Ly W x ER
then have
2 (TYBBV
( Kx KxxC)
n
2 (BV x -xx11)= 2
V x
+
n
n
2 T K
x "T
(4) n
+ 2
(
2
(VxKBBx
43

---

where (a) follows from the eyclic property of the trace and the symmetry of the kernels. Now, the cost of computing A. B and O + m²), and given these matrices, the cost of computing m
D == CB Immm and E == A B E mmxm is (nmm²). So, we are now in a position where we have to compute
2 Tr (V
2 x
xxJ (
K xx
n
n
2 Tr x K x F.)
2 2 Tr (V xxxxx* xxxx
n
but, following the exact same logic as in section B.4.2] we can compute these traces as sums of products where the majority of the elements of V x xxx x and V xx are zeros, and hence much wasted computation and storage can be avoided. Therefore. similar to equations (2T) and (22). we can compute the quantities Tr (V & K x) and Tr (Vx K x BT) with ((m)) time and storage cost, and Tr (V x E3) and Tr (V xxx with O time and storage cost.
Therefore, we have an overall storage cost of O(mn + m²), and time cost of O( + m?2)) i.e. linear with respect to the size of the full dataset D.
Remark B.14. Above we have derived analytical gradients of the objective function, and shown they can be computed in linear time. In practice one computes the gradients using JAX's [79] auto- differentiation capabilities. The authors observed minimal slowdown from using auto-differentiation.
B.11 Accelerating Objective Computation for Discrete Conditional Distributions
As outlined in C.1.3 for discrete conditional distributions e.g. those encountered in classification data, the response kernel I(-.-) -) chosen to be the indicator kernel. In this case, gradient descent on the responses is no longer possible. For herding-type algorithms it is straightforward to alternate between taking a step on the feature æ, and then, given this new æ, exhaustively search over the possible values of the paired response y.
For KIP-style algorithms, given a step on each of the features in the compressed set X, it would be very expensive to exhaustively search over each possible combination of responses in Y to find the jointly optimal combination. To reduce this cost, we take greedy approach and iteratively, response-by response-by-resoonee besrooo,,,, exhaustively search over the possible values carrying forward the optimal value of each response the next iteration. For pseudocode for these procedures see Section D.I
In this section, by treating each KIP-style objective just as a funetion of each response ý in Y, show that one can accelerate computation of the JKIP and ACKIP objective functions, reducing the cost of the corresponding exhaustive search procedure significantly.
B.11.1 Joint Kernel Inducing Points
Defining X == [ objective
Lmm]" and Ý == [81. ................................ in JKIP, we optimise the following
m k( (.,, 9,)
2
m.n.
C 1 Y)
k(o, 2,, ((y (:))
(30)
m 1,j=1
mn
Now, if one treats this objective solely as a function of a single ÿt E Y, fixing X and the remaining points in Y, then it easy to see that optimising 30 is equivalent to optimising
= 2
m
2
n
F (ū))
k(
3z ((),, ;))
k( 2z Mg,),
m
mn
j=1
j=1
2
Lm (ūr) 2
m (2.) K
K ( Ln (ūt)
(31)
m
mn
where K,, (x) = [k(z 51) k(x, Rmm and K (z) == [k( x1 .................... k(x, TT,]
(y) = [My 인1 )....... Ky, 9m.) and (y) == (ly.y))...,, ((y,,,,,,,y,)))
This reduces the
cost of evaluating the objective function by factor of m. both in storage and time. Note that if using a non-stationary kernel I(.,) ) one must avoid double counting the diagonal term in Equation 30 by subtracting 1 k( ã. (( 9.).
m
44

---

B.11.2
Average Conditional Kernel Inducing Points
In Section B. 10
we saw that the objective of ACKIP can be written
J JD(XYY) = πt 1.p..
k(a,, W 3p po
2
uyn ū.) W.) 2..)
Now, if one treats this objective solely function of single ÿt Y, fixing X and the remaining points in Y, then it easy to see that optimising the above is equivalent to optimising
Ra
=
kor,, T,) W WW Up (Z
T1
J.P.q=1
2
9r (.,
PJ=1
2
U Fp W pa (Zg 2r (a (3, Tr
12
j.P.z=1
2 n,m
Σ n
l Up 3p) (kpp H,
pJj=1
im (i:)
x K x 2 (ū:)) K xxxw; wi
(32)
(b) n
where (a) follows from the symmetry of the kernel functions and simple reordering of the terms, and (b) follows from defining w, to be the th row of W x Note that using a non-stationary kernel
:(::)) one must again subtract a correction term n (w, K Kxx K xx) I(jr,, ÿt) to avoid double counting the diagonal.
Now, the important observation to make is that one only needs to compute the terms involving X once, as we iterate through each Dt E Y with X fixed. Hence, if we ignore the one-time cost of computing W x x then this objective O(m + n). A very similar derivation holds for ACKH.
C Experiment Details
All the experiments were performed a single NVIDIA GTX 4070 Ti with 12GB of memory, CUDA 12.2 with driver 535.183.01 and JAX version 0.4.35.
As is ubiquitous in kernel methods, unless stated otherwise, we standardise the features and responses such that each dimension has zero mean and unit standard deviation.
For continuous conditional distributions, the kernel functions k X' R and I: y I are chosen to be the Gaussian kernel, defined
k(x,, x') = exp
1 x 20
x' 112 (yy = exp
1 1ly 2²11²) 20
where the lengthscales agg aq are set via the median heuristic. That is, given dataset {z, } the median heuristic defined to be
Hp = Med {||2, - 11 Isisi
with lengthscale := /HH// such that r(z, x') exp (- || -= 21112)
This heuristic is very
widely used default choice that has shown strong empirical performance [80] For discrete conditional distributions, we replace the response kernel with the indicator kernel, defined as
1ly 3 = [1 y = V/'
(0 otherwise
45

---

See Section C.1.3 for additional details on the impact of this change in kernel.
The regularisation parameter À is selected using two-stage cross-validation procedure validation set consisting of 10% of the data. In the first stage, a coarse grid of candidate À values are used identify a preliminary range for the regularisation parameter. In the second stage, finer grid is constructed within this range, and searched over. To avoid the ((n²) cost of training the KCME, we randomly sample 10 subsets of the training data of size 1000 such that the optimal value is averaged over these random training sets to determine the final regularisation parameter.
For all experiments, we the Adam optimiser [81] implementations of ACKIP and ACKH allow for an arbitrary choice of optimiser via the Optax package [82]. We set a default learning rate of 0.01 across all experiments.
sensible default choice. However, the
To provide reasonable seeds for minimisation across each iteration of JKH and ACKH, we follow the approach of [3] and draw 10 random auxiliary pairs from the training data, choosing the seed to be the auxiliary sample which achieves the smallest value of the relevant loss. In comparison, to initialise JKIP and ACKIP, we draw 10 auxiliary sets of size and choose the initial seed set to be the auxiliary set which achieves the smallest value of the relevant loss.
In order to compare the performance of the above approaches, we note that the primary goal of the kernel conditional mean embedding is approximate the conditional expectation E[ X z] for arbitrary functions h E H2 and conditioning variables z E X. Hence, to assess this approximation, we report the root mean square error (RMSH), where the mean is taken with respect to the distribution of the conditioning variable, Px-
(BI)((Y) | xx) 1 (x ,1
RMSE(C) = Ba
1
E[h(Y) |X= x,1 - -(8 (1)11)))
For continuous conditional distributions, we report the RMSE for the first, second and third moments,
as well as the functions h(y) = syn( hyy) = cos(y), h(y) = exp(-y²), hvy) = lyl and
1u()) 1920- These choices of test functions extend those chosen to evaluate Kernel Herding [
C.1 Additional Figures and Experiments
In this section we include additional figures for the experiments in the main body, and further experiments on discrete conditional distributions.
C.1.1 Matching the True Conditional Distribution
In this section we include some additional figures for the true conditional distribution compression task outlined in Section
FigureD dissllas an example of a compressed set of size m 500 constructed by each method. We note that JKH and JKIP have clearly constructed representation of the joint distribution; with the JKIP construction seemingly more structured. is interesting to note the extreme disparity between the compressed sets constructed by ACKH and ACKIP, versus the relative similarity of JKH and JKIP. We know that ACKIP achieves superior performance, hence may be the case that the greedy heuristic is particularly poorly suited to targeting the AMCMD.
46

---

Figure 9: Compressed sets of size m 500 constructed by JKH (orange), ACKH (bluc), JKIP (red),
and ACKIP (green), on the true conditional distribution compression task.
Figure 10 is an enlarged version the first subfigure Figure 2
Figure I1 is an enlarged version
of Figure 2 showing results on a larger number of test functions. In Figures 11 and 12 we see that ACKIP still dominant, achieving the best performance across all the test functions, with ACKH achieving second best performance on six of the eight considered.
47

---

10a
AMCMD S 1x Py
10-1
10
Randern Sampling
ACKH
JHH
ACKIP
KIP
Compressed Set Size
Figure 10: Results for the true conditional distribution compression task with parameters set as ag 0.5, 01 0.5, μ 1, o² 1, and of 0.5. The AMCMD2 Prj, Py x is reported as the size of the compressed set increases. For JKH (orange), JKIP (red), ACKH (blue), and ACKIP (green), we display the median performance (bold line) with the 25th percentiles (shaded region) over 20 runs. The error of random sampling (black) over 500 runs is also plotted for comparison.
Myl -y
hlys
mly -y
Myy sinly)
RMSE
p(y] ccosly)
hly1-e -
mly Ev
my 1 -1y
RMSE
127
3.'
307
12"
Figure 11: Results of the true conditional distribution compression task. The RMSE is reported across a variety of test functions, as the size of the compressed set increases. For JKH (orange). JKIP (red), ACKH (blue), and ACKIP (green), we display the median performance (bold line) with the 75th percentiles (shaded region) over 20 runs. The error of random sampling (black) over 500 runs is also plotted for comparison.
48

---

my²
sinly]
RMASE
costy)
fly) 1ypen
MASE
Figure 12: Results the true conditional distribution compression task for compressed sets of size 500. The RMSE across variety of test functions is reported, with the IQR highlighted for each method. Outliers are calculated as being above Q3 + 1.5IQR and below Qi 1.5IQR.
C.1.2 Matching the Empirical Conditional Distribution Continuous Regression
Real: this section we include some additional figures for the Superconductivity data outlined in Section Figure 13 shows the AMCMD2 Py achieved by each distribution compression method as the compressed set size increases. ACKIP reaches the lowest AMCMD, followed by ACKH, JKIP, then JKH. Figures 14 15] enlarged versions of and respeecivevl. showing results on larger number of test functions. We see that ACKIP achieves the lowest RMSE across each of the test functions, with ACKH in second for all but one. We also note that JKIP tends to achieve favourable performance versus JKH.
49

---

AMCMD 2 [Px I x, P Py
10-1
Random Sampling
ACKH ACKIP
10-2
JKH
JKIP
100
101
102
Compressed Set Size
Figure 13: AMCMD2 1Px ,r achieved by each method function of the size of the compressed sets constructed by JKH (orange), ACKH (blue), JKIP (red), and ACKIP (green), on the Superconductivity data. We display median performance (bold line) with the 25th-75th percentiles (shaded region) over 20 runs. The emor of random sampling (black) over 500 runs is also plotted for comparison.
50

---

-10
eiv) zy
hyy TV*
h(y) -y
hly - siniy)
RASSE
m(y) -costy
R(y ---
NMy 1M
:(yy - 11y-o)
RMSE
30'1
18
Figure 14: Results for the Superconductivity dataset; the RMSE is calculated against the full data estimates of B[((Y) X = æ; as the true values are not available. The RMSE is reported across a variety of test functions, as the size of the compressed set increases. For JKH (orange). JKIP (red), ACKH (blue), and ACKIP (green), wwe display the median performance (bold line) with the 25th-75th percentiles (shaded region) over 20 runs. The error of random sampling (black) over 500 runs is also plotted for comparison.
My y
Rexer
=y²
bly) =y²
hiy sinly)
RMSE
14:0
3436
N(Y) costy)
Myy 00
My) IM
fly -1y.0)
16.0
RMSE
Figure 15:
Results of the Superconductivity dataset for compressed sets of size m = 500. The RMSE across a variety of test functions is reported, with the IQR highlighted for each method. Outliers are calculated as being above Q3 + 1.5IQR and below Q 1.5IQR.
Synthetic: In this section we include some additional figures for the Heteroscedastic data outlined in Section Figures and 17 are enlarged versions and respectively showing results on a larger number of test functions. They show that ACKIP consistently outperforms the other methods across a range of test functions, achieving the lowest RMSE as the size of the compressed set increases. In particular, Figure 7 demonstrates that with m = 250 pairs in the compressed set, ACKIP attains the lowest median RMSE on seven out of eight test functions. For the remaining function, all methods exhibit similar median performance. This highlights the advantage of directly compressing the conditional distribution with ACKIP, rather than targeting the joint distribution with JKH or JKIP. Finally, we note that JKIP consistently outperforms JKH across all test functions.
51

---

6ly1 -
My]
H(y) =y
Mly sinly)
ROASE
hrg costy)
14199 =
Ney - 11yx0)
RMSE
Figure 16: Results for Heteroccedastic data with parameters set as a = [3, -, 6, 6]
[1. 2.0, c c:= [-5, 22, 2, 5] of 0.75, and ož = 0.1. RMSE is reported across a variety of test functions, the size of the compressed set increases. For JKH (orange), JKIP (red), ACKH (blue), and ACKIP (green), we display the median performance (bold line) with the 25th-75th percentiles (shaded region) over 20 runs. The error of random sampling (black) over 500 runs is also plotted for comparison, as well as the performance of the full data (purple).
hyr-y
tut
hlyl -y²
bly) -y*
36307
14
RM55
20"ge1
12030
Myy
My merd
3418
hty
hlyl =1ycs
BMSE
12917
14:8
12607
32a
Figure 17: Results for Heteroscedastic data for compressed sets of size m = 250. The RMSE across a variety of test functions reported, with the IQR highlighted for each method. Outliers calculated as being above Q3 + 1.5IQR and below Q1 1.5IQR.
Figure 18 displays an example of compressed set of size 250 constructed by each method. We note that JKH and JKIP have clearly constructed a representation the joint distribution, whereas ACKH and ACKIP have constructed something that is more difficult to straightforwardly interpret.
52

---

Figure 18: Compressed sets of size m 250 constructed by JKH (orange), ACKH (blue), JKIP (red), and ACKIP (green), on Heteroscedastic data.
Figure 19 shows the 2MCMD²
[Px.PrIx Pyix achieved by each distribution compression
method as the compressed set size increases. ACKIP reaches the lowest AMCMD, followed by JKIP. JKH and ACKH perform similarly to random sampling, though ACKH initially outperforms JKH and JKIP before being limited by its greedy nature, allowing JKIP to surpass it, and JKH to match it.
53

---

AMCMD2 P P X, PyI
10-1
10-2
Random Sampling
ACKH ACKIP
JKH
JKIP
100
101
102
Compressed Set Size
Pyx. Py|x achieved by each method function of the size of the compressed sets constructed by JKH (orange), ACKH (blue), JKIP (red), and ACKIP (green), on the Heteroscedastic data, We display the median performance (bold line) with 25th-75th percentiles (shaded region) over 20 runs. The emror of random sampling (black) over 500 runs is also plotted for comparison.
Figure 19: AMCMD²
Ablation Study: Using the same setup for the Heteroscedastic data, we repeat the experiment with the Gaussian kernels replaced by inverse nulti-quadratic kernels. report the results in Figures 20
and 21 where that ACKIP still achieves the best results across variety of test functions.
54

---

Inverse Multi Quadratic Kerne
hly -y
hty
hiy? sinjyl
10
RMMSE
RUA -cosiy!
nly)
My1 = M
hiy - 1sy
RMSE
12¹
20'
27'
Comprassed Set Size
Compressed Set Size
Compressad Set Size
Compressed Set Size
Figure 20: Results for Heteroscedastic data with IMQ kernels. RMSE reported actoss a variety of test functions, as the size of the compressed set increases, For JKH (orange), JKIP (red), ACKH (blue), and ACKIP (green), percentiles (shaded region) over 20 runs. The error of random sampling (black) over 500 runs is also plotted for comparison, as well the performance of the full data (purple).
display the median performance (bold line) with the 25th-75th
Inverse Multi Quadratic Kemee
h(y) yy
hly) =y²
fly)
hlyl - sin(y)
sandan
RMAE
Myy cosly)
blyl -
hyyl
hly? - 11ysc0)
R05S
Figure 21: Results for Heteroscedastic data for compressed sets of size m 250 with IMQ kernels.
The RMSE across variety of test functions reported, with the IQR highlighted for each method. Outliers are calculated being above Q3 1.5IQR and below Q 1.5IQR.
Wall-Clock Time: In Section D.2 we derive the computational and storage complexity for each of the methods introduced in this work. In Figure [2] and Table I we report the wall-clock time for the Heteroscedastic data experiment. Despite JKIP and JKH having the same time complexity, we see that JKIP is significantly faster. noted Section D.2.5] the algorithms in this paper were implemented using JAX. JAX enables Just- In-mme (JIT) compilation, which significantly increases execution speed. However, to achieve this speed, JAX relies on an immutable array structure, meaning the arrays must not change shape during program execution. As result, JKH and ACKH cannot fully leverage the speed benefits of JIT compilation, as the size of the compressed set, and hence the corresponding arrays, increases at every iteration. Conversely, the arrays considered in JKIP and
55

---

ACKIP stay the same shape throughout. This presents a notable practical advantage of JKIP and ACKIP over JKH and ACKH.
Method
Wall Clock Time (s)
JKH
9.47 + 2.37 0.84 0.081
JKIP
ACKH
318.81 + 40.17
ACKIP
11.42 + 0.04
Table Wall clock times (in seconds) for each method over twenty runs, mean and standard deviation reported.
ACKH
JKIP
ACKIP
JKH
Wall Clock Time (s)
Compressed Set Size
Figure 22: Timings for Heteroscedastic data.
C.1.3 Matching the Empirical Conditional Distribution Discrete Classification
For classification tasks with C possible classes, we replace the Gaussian kemel the responses with the indicator kernel I NC x No + [0, defined by
1( 3²) = { y y O otherwise
where NO : == possible. Moreover, solving the optimisation problems of JKH, JKIP, ACKH and ACKIP now consti- tute a mixed-inte integer programming problem, which known to be NP-complete. Various heuristic approaches exist for problems of this type, such relaxation baseed methods (e.g., continuous relax- ations followed by rounding), greedy algorithms, and metaheuristic strategies like genetic algorithms simulated annealing. We develop simple two-step optimisation procedure based exhaustive search, leaving investigating the above techniques the context of our algorithms for future work.
In this case, standard gradient descent on the responses is no longer
For JKH and ACKH, alternate between performing gradient step the feature and selecting the optimal response class via exhaustive search. For JKIP and ACKIP, after each gradient step X, we iterate over the responses in Y. updating each in turn with the optimal class by exhaustive search, carrying forward these selections. It important to note that one can reduce the cost of evaluating JKIP and ACKIP objective functions significantly when X is fixed; see Section B. for a derivation of the relevant objectives and Algorithms 7 and g for the pseudocode.
56

---

For classification tasks with C' classes, we report the overall classification accuracy and Fl scores, as well the RMSE for the indicator functions (y) (ymi). where 1...., C. As shown in 33 the KCME naturally functions as multiclass classification model, since
Blb(Y) x =[[ X x) = P(Y = x),
which expresses the class probabilities given X. Moreover, the empirical decision probabilities are guaranteed to converge to the true population probabilities (Theorem I, [33 unlike, for example in multi-class SVCs and GPCs. However, in the finite case, the predicted probabilities are not guaranteed to lie in the range [0, 1.. nor form a normalised distribution. order produce valid distribution,
we clip-nonne normaliee the estimates (Equation 6, [33).
Synthetic: We generate an unbalanced 4-class dataset using the multinomial logistic regression model, where conditional class probabilities are given by PP(Y 0
X = x)
T+E,_ exp(A
and IP(Y = X = x)
exp(A..a)
S k < 3, and
Px is a 2D Gaussian mixture
I+Σ,
exp(8)
10
1
45
model with 100 components. We assign classes using / =
and, to ensure
40
45
40
10
class overlap, introduce additive noise ~ (O, 100) to the exponential. This setup results in class proportions of approximately 32% (class 0), 12% (class 1), 19% (class 2), and 37% (class 3).
Figures 23 and 24 show that ACKIP achieves clearly superior performance versus ACKH, JKH and JKIP, both predicting the class probabilities, well in overall accuracy and Fl score, achieving parity with the full data at only 3% the size.
hly) = -
h(y) = 1
6.0
Classification Accuracy
6.8
RMSE
6.6
1x18
0.
Rardbn
10.
hly) = =1y=22
n(y) = =1y-
04397
Score
0.6
RMSE
0.5
0.4
0.3
2437
0.2
0.1
Figure 23: Results for Imbalanced dataset. RMSE is reported across variety of test functions, as the size the compressed set increases. For JKH (orange), JKIP (red), ACKH (blue), and ACKIP (green), we display the median performance (bold line) with the 25th-75th percentiles (shaded region) over runs. The error of random sampling (black) over 500 runs is also plotted for comparison, as well as the performance of the full data (purple).
57

---

h(y) 1(y-0)
hly) (y-1
0:99
Classification Accuracy
6:07
RMSE
0.80
0.04
244.0
hly) = 23
Myy) =1--)
Score
RMSE
0.00
640
600
085
6:0
Figure 24: Results for Imbalanced dataset for compressed sets of size m = 250. The RMSE across a variety of test functions reported, with the IQR highlighted for each method. Outliers are calculated as being above Q3 + 1.5IQR and below Q1 - 1.5IQR.
In Figure 25 we see that ACKIP achieves by far the best AMCMD, noting that the final value achieved effectively zero. Due floating point errors in the computation of AMCMD² P Pr it can become slightly negative, resulting in the line leaving the log-log plot. We also see how the herding optimisation approach hinders ACKH as initially matches ACKIP, but ends up performing worse than random. Finally, note that JKIP outperforms JKH. which only matches random.
58

---

10a
100
AMCMD 2 Pxx, Py PY
10
10-2
10-3
10
Random Sampling
ACKH ACKIP
JKH
10-5
JKIP
100
101
102
Compressed Set Size
Figure 25: AMCMD2
[Px, Pr|x ,y achieved by each method as a function of the size of the compressed sets constructed by JKH (orange), ACKH (blue), JKIP (red), and ACKIP (green), the Imbalanced dataset. We display the median performance (bold line) with the 25th-75th percentiles (shaded region) over 20 runs. The error of random sampling (black) over 500 runs is also plotted for comparison.
For completeness, in Figures and 27 we also include an example of the compressed set constructed by each method, well the corresponding decision boundary.
59

---

Class Class Class Class
Figure 26: Compressed sets of size 250 constructed by JKH (top left), ACKH (top right), JKIP (bottom left), and ACKIP (bottom right), on multi-class classification data.
60

---

Full Data
JKH
ACKH
JKIP
ACKIP
Random
Figure 27: Decision boundaries of the KCME model estimated using compressed sets of size M = 250, constructed by ACKH, JKIP, and ACKIP, on the Imbalanced dataset. For comparison, we also include the decision boundaries of the full-data model and model trained on uniformly random subset.
Real: We use MNIST 83 34
where we subsample down to 000 due to memory limitations,
splitting off 10% for validation and another 10% for testing. Figure 28 shows that ACKIP achieves the lowest AMCMD, with JKIP doing second best. In Figures and we see that this translates to improved performance in estimating conditional expectations, with ACKIP achieving vastly superior performance versus the other methods, with similar classification accuracy and score to the full data model, with just 3% of the data.
61

---

100
AMCMD Pxx X
10-1
Random Sampling
ACKH ACKIP
JKH
JKIP
100
101
102
Compressed Set Size
Figure 28: Results for the MNIST dataset. We show the AMCMD2 each method function of the size of the compressed sets constructed by JKH (orange), ACKH (blue), JKIP (red), and ACKIP (green), on the MNIST data. We display the median performance (bold line) with the 25th-75th percentiles (shaded region) over 20 runs. The error of random sampling (black) over 500 runs is also plotted for comparison.
Pxx Py x fy achieved by
62

---

h(y)) 10y
h(yy 1
(n6x 11y=22
bly) -
RMSE
4412
m(y) = 1 12
2037
72 11
nnly = 1gy
hiy? 11y
3450
RMSE
381
54177
14177
64297
n(y) = 1:y=8
m(y) 1(y
0.8
Accuracy
F1 Score
RMSE
0.6
0.
0.2
17 0.0
107
10
30
20'
13'
Figure 29: Results for MNIST data; the RMSE is calculated against the full data estimates of E[K(Y) X = xig] as the true values are not available. RMSE is reported across variety of test functions, as the size of the compressed set increases. We also report the overall classification accuracy and FI score, comparing against the full data performance. For JKH (orange), JKIP (red), ACKH (blue). and ACKIP (green), we display the median performance (bold line) with the 25th-75th percentiles (shaded region) over 20 runs. The error of random sampling (black) over 500 runs is also plotted for comparison, as well as the performance of the full data (purple) for classification accuracy and F1 score.
63

---

My] = 07
fly) =1 (y-1)
Hy)=
hiy = 1y-
121
RMSSE
1130
1400
hyy 4
hly) 5(y
M(y =
nly) = 1y-
16"
12"1
RMSE
1(
h(y) 9
2.500
0.50
1:500
0.00
Accuracy
2.815
Fl Score
RMSE
2.50
0.65
0.823
3800
075
Figure 30: Results for MNIST data for compressed sets of size 250; the RMSE is calculated against the full data estimates of EY)(Y) X = æi} as the true values are not available. The RMSE across a variety of test functions is reported, with the IQR highlighted for each method. Outliers are calculated as being above Q3 + 1.5IQR and below Q1 1.5IQR.
C.2 Flexibility of AMCMD versus KCD/AMMD
In this section demonstrate how the increased flexibility of the AMCMD allows for application tasks that AMMD/KCD are not suitable for.
N'O, o²) with μl, 0², of chosen such that dix dpxx are bounded. These three distributions are also clearly absolutely continuous with respect to each other, hence the conditions on the distributions in Theorem 4.1 are satisfied. Importantly, we have Px & Pxx * Px=, and thus the AMMD/KCD is not defindd for this setup. Now, let fa R be function with
Let Px = NN,,, o²), Px = -N(u,, ""), and Px- :
the Madon-Nikodym derivatives dPx dP
- a (x +o+0 a)² if x < -a
fa
x if <
(x a)² if >>>
for a I., and let IPy := NN oz), and Pyxx'== == N() Then, we have that Pylx== Py"x'== for x E [-a,aa a] and PyJx== * Py'x'= for all æ & [-a,a], The AMCMD allows to detect this change in behaviour over regions by changing the location of the weighting distribution x see Figure 31 In fact, using Lemma 4.3 Figure 31 to be approximately equal to 1c-2.
we estimate the AMCMD in
64

---

(x,)) - 1(x, n M(X. (x,y') -xy))~(x,M)
Px
Responss Space
Y=X
xx=Xx)
-4
Feature Space
x
Pl" Fxx
X
PDN
RND
x
35 Teature Space
35
Teature Space
Figure 31: The top plot illustrates the data space, with a = 0.4, = 0.5, and o 0.1. Here, pairs sampled from xx (red) exhibit the same linear relationship as pairs from Px y (bluc) around zero, where the density of the weighting distribution P'x is concentrated. Away from zero, the relationships diverge, and xp is chosen to have little mass in these regions. The bottom-left plot shows the probability density functions of x (red), Px (blue), and Px- (orange). The bottom-right right plot displays the Radon-Nine Madon-Nikodym derivatives dP x= (red) and x= (bluc), which are clearly bounded dP
di
in this case.
In contrast, the relative inflexibility of the KCD/AMMD would mean one would not be able to detect over which regions of the conditioning space the conditional distributions are equal; see Figure 32 for an illustration of this. Using Lemma we estimate the AMCMD to be approximately 0.5.
Response Space
Yex
Y-9X)
POF
Feature Space
Figure 32: The data space where Px-
Xx Px- = N(0,03), with 0² 0.5, a = 0.4.
C.3 Targeting Family of Conditional Distributions Exactly
In order to construct a compressed representation that exactly targets a family of conditional distribu- tions PY Frjx, require access to analytical expressions for the expectations
ExpPy [k(x,, x' d') x²)] and ((a.)))-x, [M x (v))l((
(33)
for arbitrary x', x E X' and y' E V. Furthermore, in order to compute the exact AMCMD between the true family of conditional distributions and the family of conditional distributions generated by the compressed set, we must also able to evaluate
Ex-Tx Illey x== l.
(34)
In general we cannot exactly evaluate the expectations in 33 and 34 restricting our attention to specific choices of the kernel functions k X
however it is possible by
X R andd/ L y y - R.
65

---

and specific data generation process. In particular, we set
k( x²) = exp
Vv,,')== = cxp (x x2)²). (z-=')²)) 2a
1
1 2aq
(y
y
Le. Gaussian kernels, with ogs, as Rz0. Moreover, we let Px NNH,, 0²), and given coefficients E R we let y = + aiæ + where e ~ NNO, i.. Prix- Naa + a a, o.)).
C.3.1 Deriving the Marginal Expectation
In this section, we derive the marginal expectation in 33 under the conditions on the kernel and data-generating process previously laid out:
EawPx [k(x,, x' [b(x,,1)) = / k(x, x' )k(æ,, x²) x")Pxx (dx)
V2TT22 / exp (
jo x/}²
x - x²
20 10 119²) do.
20
20
Now,
1
(
x¹) 2-_
(x-
x²
xx 12)
20
2
20
20
(x²
2xx'
+ x²2)
(x² 2xx" "
+ x²²)
(x² - 200 + 12)
20k
7
20
2
20
2
(x'
+ x²")
12
(x. + x2))
+
2
02
a1
02
20
20
A
112
(x
"2)
2
+
Bæ
202
20
where A: ==
+
2
B =
11
+
+x")
Completing the square, we have
02
0z
A x
A
2B
A
B
2
B
2
Bæ
x²
A
A
and therefore write that,
Ex-Px x kk(,, x ")(x) x")]
1
1
1
2
X
exp
200
(xt
x²)²
20
(æ
x²)²
20
(x
1u)
dæ
A
B
2
B
2
112
(x.2
+ "2
exp
dæ
2
Xx
A
202
2a 2
1
A
B
2
(x + x22)
A
B
exp
exp
dæ
V V
A
20
20
X
A
1
A
B
(x²² 2 + x
exp
A
20
20
C.3.2 Deriving the Joint Expectation
In this section, we derive the joint expectation in (33). under the conditions on the kernels and data-generating process previously laid out. We first derive the joint distribution.
We have that
fx,y y) = fx(xx)fvxx=all = 2TOO.
exp
1
(x:
112
(y (ag + a1zz))2
2
20
66

---

where using
B[X] = μ4 E|y] = Blao + 01 X] = og + 01/4,
Var(X) = o², Var(Y XX) =
Var(Y) RRIVar(Y X)] + Var(IllV X]) 0.² + ajo²
Cov(X, Cov(XX, ao +a1x) ai Var(X) ajo²
((o0 I taa)) ( (gg
a10² a¹ oz )
ajt²
we notice that (X,Y) ~N
Now, want to derive the expectation B(ay))Rxx [k(x, x' (y, y')l for arbitrary w' X and y E E::
(xxx))xPxx 1k x My / k(x x' Myy y v ydddy
where -(.,)) and I(:,)) are both Gaussian kernels. We need this integral to end up in the form
J exp -- Aw + +b w + + du
for = (x, T as by completing the square, it can be shown [85 that
bow [ exp 1 Aw b w + t dw
2x
1 b c+
A 1-bb)
exp
LAIE
Let us first interrogate the product k(x,, x. ((y, (/y,yyy)))) y'):
k(x x' (B, 3/)
exp
(x
x²)²
207 (y w/)2)
1
20
k 1
[a (ar x') + az - y)'²]
exp
20
2x x + x² + az
22' + 2/
exp
20
1
x
22
T
x
x2 + +oyy²
exp
20 7
y
0
y
+
20
y
+
x
x2
y
exp
w
w
+
y
w
20
2a²
= exp
(
w
Aiw + b7 w +
where A
at
0
0
1
b
=
(x//af y//a
and C₁ =
2az
x²
2a
y
Now, we need to write
a?
(x, in the same form:
[xY(x. v) [x(x))vix== 2T0O. exp
1
20 (xc - 11)2
1
(y) (an + a1z;))²
20
(-
2020? (~20203 [02(20 - -11² + 2² - (ag + a12)))3])
exp
2TTO.
67

---

Now,
o.(x - 21² + o² (ao + alæ))?
ox²² - 24 1²) + 03²² 2y(as + (1x) (ag + a1z)
co? 2u n²) + (y²² 200y 22 ay agj 20ga + af
(o? + afo²) + x 2po 2a0az0²) + (² + y6 (1go0a))) 1ull-2110") (ag0² + x2)2)
Tw ( + af a9
0
+ [2agajo² 2n0
ago² + p2oe
-ajo a²
-2000²
hence,
(x,
exp
2020? [02(x 11)² + 0 (ag + a]x=))a]]
2nOO.
w
0:2 + 0f0²
-a10²
22arai0²
2uo??
+ ago² + m?o?
2no0.
exp
2020
010
+
-2ago²
1
0
112
exp
--
w
o
w
2nTO.
2r
d
1
exp
w
Ayw
+ by w + C2
2TTTT
2
#/4
Rud
of
where A2 :=
c
0.
b2 =
and C2
2g
20
20
a
Therefore, we have that
P( [k(x, x (y y')l
=
=
k( ('e, ((,, y fxxy (ax y) dxdy
(-1w w Mil - blw + exp (- w A2w + bJ + + du
exp
2nao
R2
2
1
1
w (Ai + +22 + (b, + b2) To + t0z dw
exp
2Too,
g2
2
1
exp
w
T Aw + +b wwc +c dw
2nao
R2
2
1
2TT
A A b)
(ct 1 b A A
exp
c+
- b
exp
2TOOG
|A|
2
Vo2o?|A1
2
where = A1 + Ag, b = b + by and c = C1 + +
C.3.3
Computing the AMCMD Exactly
In order to compute the AMCMD exactly, we require an analytical expression for (34). First note that have
|y||x==l 2| (py X My|x
Ey-Pyixes |a||== (y)
Ey-PPix-e Eg [1 (y.3')]]
where the second and third equalities follow straightforwarddyy from the definition of the KCME. Now, the first step is to derive an analytical expression for
Ey - [1 (g. 9'),, y E y
68

---

Writing, f(x)= = ag + a1 we have
By'ney x-= y')l = (ly, "u.y")p (y))d
=
/ exp
2a² (v' - -1)²
V2T0?
exp
(- 1
(-20 20?
(y' - f(x))) dy
2TO? / exp (- 2aF
1 (v' 4)²²
1
(y' {(x)))² dy.
20?
Now,
(y'
- y)²²
( -(()))²
207
20
(y² 2yy' +²)
1
22y' [(x)) (y²-2y)
[(x)²)
20
20?
1
y²
1
+ y
y
+
f(x)
y²
f(x)
2
2
af
o²
207
20²
y²
(x)²
2 y
By
20
20
where A =
1
+ 1 σ.
and B =
+
[()]
Completing the square, we get
0j
o?
A y² By
A
2B
A
B
B
y
y
2
A
and therefore we can write that,
Egg-Prix [[y 3')
1
cxp
(g'
y)²
(v/
f(x))2 dy
2m
20
20
y
A
B
B
y²
f(x)2
exp
dy
V
2
A
20
20
A
B
2
(xx)
A
B 2)
exp
exp
dy'
2
20
20²
2
A
1
A
B
2
y²
f(x)2
exp
A
2
A
207
20
We can further simplify by removing the unwieldy constants A and B, writing that
Eg E [1,,, s/)]
y²
f(x)²
B2
exp
VA
2A
207
20?
y²
yf
f(x)2
y²
f(x)2)
V Ao? exp
2A
+
070?
o!
2n²
20
1
1
A
yf(x))
1
A
1)
VAoe
exp
2A
y²
2
aPo?
+ f(x)2
y²
yf(x)
f(x)?
VAo?
exp
2A
07
+ +2
af
afo?
ly f(x))²
exp
Ao
2( + 02)
69

---

The next step is therefore to compute,
By-Frix-o
[1 [y,,'))
V Ao?
1
E B
Prix=
exp
2(a dQ)
1 f(x)))
/ exp
20 1 - f(xx)2
1
3 f(x)1² dy
exp
VA V2T0² ly
2(a - -??)
1
/ exp
20 of
yy f(x)]² dy
o? 22T
02 (0 + att)
1
(o + of)
o? + aî A2?? + +af)
o? + a7
2T
0.2 2
20 + of
((1+ 0²
(20 + t
Therefore,
Ex-xx [|1x||==11]]]
= -Ex=Px
E FyrPP Sy-PPrxxe prx== Byy Pyine [y, y []]]
o? + az
o? + af
ExpPx
o² (1
(207 + +x7)
((1+
1
o²
(20 + of
+
where that the integrand with respect to the expectation over Px is constant. Note that the above computations hold for arbitrary / X' - R, however we require that the error has constant variance of- If the error constant and evolves as a function of æ, then the final expectation with respect to P may become very difficult to compute exactly.
D Algorithm Details
In this section we include additional details about the algorithms developed in this work including pseudocode and complexity analysis.
D.1 Pseudocode
In this section we include pseudocode for the algorithms introduced in this work, including gradient- free variants of the Kemnl Herding type algorithms suitable for X' * Ied and y & RR. In all gradient-based algorithms,
pseudocode assumes standard gradient descent. practice, however, any gradient descent variant may be used. In our implementation, we employed the Optax [82 package, which provides access wide range gradient-based optimisation methods, including ADAM (81), which used in our experiments.
70

---

Algorithm Joint Kernel Herding
Input: Dataset DD = {( v:) ) C X Coreset size M E N, Feature kernel k: X X' - R.
Response kernel 3 x y IR, Candidate batch size N, Maximum iteration number Step size
for t = 1 to do Uniformly at random, select C' candidate pairs {(0,, D.) from
fo = 1 to C do
Estimate S f- _ (Zt, Di) using equation 12
end for
1" arg min S:
( 91
(Ii+, D:-)
for to T do
Compute V (ā új) using equation 13
Compute V v, (ā,. ú;) using equation [4
#1+1 2j aV x Cp 1-1 (z.. Új)
Mj+1 yj vV - ( Ui)
if converged then break end if end for
Add the final optimised pair to the compressed set:
C. C-- ( ÿ)}
end for return Cm
Algorithm 2 Average Conditional Kernel Herding
Input: Dataset D = {(2;, }=) C X'xyy Coreset size M E N, Feature kernel k X' X' + R.
Response kernel / y ) + R, Regularisation parameter À E R R>o, Candidate batch size C N,
Maximum iteration number T E N, Step size E Ryo
for t = 1 to m do Uniformly at random, select C' candidate pairs {(T,, D from for to C' do Estimate S < -P,((,,, y:) using equation 9 end for i* arg min S: (01. 91) f (Zir, D..)
for
to T do Compute V -. ( "id..9) ú)) using equation 26
Compute V v,g,, (m., ú;) using equation 25
1j+1 + 2, aV _. (",.
Új+I + új aV, (
if converged then break end if end for
Add the final optimised pair to the compressed set:
C. C.-1 U (ã, ÿ)}
end for return Cs
71

---

Algorithm 3 Joint Kernel Inducing Points
Input: Dataset DD = {( Vi) y C X X, Coreset size M E N, Feature kernel k: x X' - R.
Response kernel 3 x y IR. Candidate batch size N, Maximum iteration number T, Step size
Uniformly random, select C' sets of candidate sets {(X,, Yi) from D, |X,]|
Y M.
for i I.... to C do
Estimate S < C (X;, Y,) using equation ( end for
arg min S (X,, 11) - (Xi., Y
for j = 1 to T do
Compute V Vx x (x,, Y,) using equation (19)
Compute V y _ [X, Yj) using equation 20
X,+1* X,
V x L X Yj)
Y5+1 y, a a L (X,, Y,)
if converged then break end if end for
return (X, Y
Algorithm 4 Average Conditional Kernel Inducing Points
Input: Dataset DD [xx, y: y;)) C X'xy, Coreset size M E N, Feature kernel X' X' + R. Response kernel / y x y + R, Regularisation parameter X E Ryom Candidate batch size C N, Maximum iteration number T, Step size
Uniformly random, select C sets of candidate sets {(x,, Y1)C from D, |X Y M.
= L....O C
for 1 to C do
Estimate S; < [XX Yi) using equation
end for
i' arg min S (X,.Y) - (X,,, Y..)
for j = 1 T do
Compute V JD X j, Y,) using equation 28
Compute V J X j.
using equation 29
X,+1 X, a V
(X,.)) Y,)
YJ+1 + Y, a y J P (X,, Yi)
if converged then break end if end for
return
X)
72

---

Algorithm 5 Gradient-Free Joint Kernel Herding
Input: Dataset ID = ( y:) } s=1 C X Coreset size M E N, Feature kernel k xxx - R. Response kernel
R, Candidate batch size C' E N
Initialise Co = 0 fort= 1 to do Uniformly at random, select C' candidate pairs {(0,, 9.)) from
for 1 to C do
Estimate S f- _ (Zt, Di) using equation 12
end for
8" = arg min S:
C U ( Fz-))
end for return CM
Algorithm Gradient-Free Average Conditional Kernel Herding
Input: Dataset D = (2),, y:) } C X y,, Coreset size M E N, Feature kernel k X'x - R.
Response kernel / y y F. Regularisation parameter X R=0, Candidate batch size C
Initialise C. 0 for /. = to do Uniformly random, select C' candidate pairs ((F,, D from D for i= 1 to C' do
Estimate S, + G._, (ā;, 9:) using equation 99)
end for
- arg min S;
C- C--1 U (ã,,, y. }}
end for return Cı
73

---

Algorithm 7 Joint Kernel Inducing Points with Exhaustive Search
Dataset DD = {( yr) y:)) C X x y, Coreset size M E N, Feature kernel k x - R, Indicator response kernel y x + R, Candidate batch size E N, Maximum iteration number T, Step size Set of possible classes A == (0, ..)
Input:
Uniformly random, select C' sets of candidate sets {(X,, Y.) from D, |X, = I..... for i to C do
YY M.
Estimate S < C (X;, Y,) using equation 4 end for
arg min S (X1, 11) - (Xi., Y
for j = to T do
Compute V [ (X, Y,) using equation (19)
Xj+1* - X, -V (X
for to do
Using equation
31 compute FD (3:) for each possible value of ÿ, E (0, .. a}
Update Y, with the optimal choice end for if converged then break end if end for
return (X,
Algorithm 8 Average Conditional Kernel Inducing Points with Exhaustive Search
Input: Dataset D { y: ) C X y, Coreset size M E N. Feature kernel k X' X' - R. Indicator response kernel | y x - R. Regularisation parameter À E Ryo Candidate batch size
C E N, Maximum iteration number T, Step size a, Set of possible classes A == {0, (0,1,...,,0 ()
Uniformly random, select C sets of candidate sets
{X,, Y1 from D, |x,
| M,
1, C
for to C do
Estimate S; + (D( Yi) using equation end for
arg min S. (X, Y1) - (X,,, P/-)
for j = to T' do
Compute V JD X using equation 28
X,+1 < X, aV x J
to m do
Using equation 32). compute RD R²().)) for each possible value of ÿ; (0, 1, a.
Update Y, with the optimal choice end for if converged then break end if end for
return (X, X)
74

---

D.2
Complexity Analysis
In this section we derive the overall storage and time complexity of constructing a compressed set of size m, where we use > m datapoints to estimate the objective functions of JKH, JKIP, ACKH and ACKIP respectively. The results are summarised in Table
Algorithm
Time Complexity
Memory Complexity
JKH
(m2 + mn)
O + n) ( + mn
JKIP
(m2 + mn
ACKH
O 0m + m
O + m
ACKIP
O O(m² + m²n)
O(m² + mn)
Table 2:
Time and memory complexity of different algorithms.
D.2.1 Joint Kernel Herding
From Section B.3 we know that each gradient computation of JKH has O(m + n) storage and time complexity.
Storage cost:
The overall storage cost is just the cost storing the gradients of the last iteration, i.e. (m + n), that is, linear in the size of the target dataset
Time cost: Assuming we take T gradient steps per optimisation each pair in the compressed set, then the cost of the m iteration of JKH is O((m + n))). Therefore, the final cost is
(mmm+ +1 + mn T O(mm² + mn) TT)
(i+
i.e. linear in the size of the target dataset
D.2.2 Joint Kernel Inducing Points
From Section B.4 we know that each gradient computation of JKIP has O(m² + mn) storage and time complexity.
Storage cost: The overall storage cost (m + mn) i.e. linear in the size of the target dataset n.
Time cost: Assuming we take J gradient steps, then the final cost of JKIP is simply O((m² + mm))) ie. linear in the size of the target dataset n..
D.2.3 Average Conditional Kernel Herding
From Section B.9 we know that each gradient computation of ACKH has Omm² + mm) storage and O(m² m²n) time complexity.
Storage cost: The overall storage cost Om2 + mm) i.e. linear in the size of the target dataset n.
Time cost: Assuming we take T' gradient steps per optimisation of each pair in the compressed set, then the cost of the mh iteration of ACKH is O(mm m²n)l)) Therefore, the final cost is
m7a
mmm + 1)
2 m(m + 1)(2m + 1) T
+NNNT==
Om +m'n)
that is, linear in the size of the target dataset but suffering from quartic cost in
D.2.4 Average Conditional Kernel Inducing Points
From Section 1. we know that each gradient computation of ACKIP has O(m² + mn) storage and O(m3 + m²N) time complexity.
75

---

Storage cost: The overall storage cost is O + mn) i.. linear in the size of the target dataset n.
Time cost: Assuming take J gradient steps, then the final cost of ACKIP is simply O((m² m²n)J) i.e. linear in the size of the target dataset n, but suffering from only cubic cost in m versus quartic for ACKH.
D.2.5 Discussion
Experimentation suggests that the number gradient steps required by JKIP and ACKIP to achieve convergence is of the same order as JKH and ACKH, i.e. J T'. Consequently, JKIP and JKH have the same time complexity, but JKIP incurs slightly higher storage cost due to an additional factor of m, which arises from the joint optimisation of pairs in the compressed set.
For ACKIP and ACKH, their storage costs are identical, as the nature the ACKH objective prevents it from being expressed solely in terms of the newest pair in the compressed set (unlike in JKH). same property causes ACKH to have an additional factor of m in its time complexity compared to ACKIP. This difference becomes significant in complex problems which call for large m, more generally when n is very large.
Throughout, we have omitted the contribution of the feature dimension d and response dimension p from the stated time complexities, as is implicitly assumed that in the distribution compression context, >> d, p. For commonly used kernels, evaluation is typically linear in d or so most, one should expect an additional multiplicative factor of d + p.
The algorithms in this paper were implemented using the free, open-source Python library JAX (79] JAX enables Just-In Insmee-Timee (JIT) compilation, which significantly increases execution speed. However, to achieve this speed, JAX relies on an immutable array structure, meaning the arrays must not change shape during program execution. of JIT compilation in their current form, as the size of arrays increases at every iteration. Conversely, the arrays considered in JKIP and ACKIP stay the same shape throughout. This presents notable practical advantage of JKIP and ACKIP over JKH and ACKH in the JAX implementation.
result, JKH and ACKH cannot fully leverage the speed benefits
76


Reviews:
[{"review_id": "VdxpLLRYRx", "reviewer": "Reviewer_XMB6", "summary": "The authors propose a novel distribution compression method specifically designed to compress conditional distributions, addressing a gap in existing techniques (e.g., Kernel Herding) that primarily focus on marginal or joint distributions. The method belongs to the kernel family, minimizing the maximum mean discrepancy (MMD) between kernel embeddings to yield a distilled dataset that best represents the original data. To measure differences between conditional distributions efficiently, they introduce the AMCMD metric. Two optimization approaches for MMD minimization are developed and compared: (a) A greedy algorithm (ACKH) with linear-time complexity (when using a specially designed estimator), (b) A non-greedy, joint-optimization method (ACKIP) with $O(m^3 + m^2 n)$ complexity, which is a factor of $m$ faster than ACKH, where $m$ is the cardinality of  a compressed dataset.\n\nA conventional compression algorithm for marginal distributions is also extended to the joint distribution case to provide a fair comparison to the methods of the same family. An experimental evaluation is conducted to benchmark all the four approaches considered. The results suggest that the proposed conditional approach is superior.", "questions": "1. What are the contemporary neural approaches (or methods of other, non-kernel families) for distribution compression? How does your method performs in comparison to them?\n2. Are there any kernel preferences specific to the task in question (kernel embeddings construction, distribution compression)? Why have not you tried other kernels?\n3. How does your method scale with dimensionality (in theory and in practice)?", "limitations": "The authors discuss limitations of their method throughout the text. However, other, more practical limitations are overlooked; see **Weaknesses**.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\nThis work addresses an important challenge in machine learning: reducing dataset size without significant quality degradation, which could enable faster model training and inference. The study is both comprehensive and mathematically rigorous, with clear presentation. Experiments on synthetic data and the superconductivity dataset demonstrate that the proposed conditional approach consistently outperforms joint distribution methods and random subsampling. Additionally, the Appendix provides extensive supporting details.\n\n**Weaknesses:**\n\n1. The background review focuses exclusively on kernel methods, omitting discussion of non-kernel approaches. The experimental comparison similarly fails to include non-kernel baselines, limiting the perspective on the method's relative advantages.\n2. While distribution compression has critical applications in generative modeling, computer vision, speech, and NLP (domains characterized by high-dimensional data) the evaluation is conducted primarily in low-dimensional settings. The authors use only one real-world dataset and notably avoid addressing their method's scalability with increasing dimensionality.\n3. The analysis concentrates on AMCMD and RMSE for test function expectation approximations, while downstream task performance (e.g., regression/classification accuracy using compressed data for training ML models) would provide more practical insight. This omission leaves the method's real-world utility unclear.\n4. The argument for the consistency of the proposed AMCMD assumes that the distributions of $X^*$ and $X$ are equal (Corollary 4.4). However, the original definition emphasizes the use of a distribution different from $X$, rendering the argument non-rigorous.", "was_revised": true, "final_justification": "No more comments from my side, I will keep my rating at 5.", "rebuttal": "We thank the reviewer for their time spent reviewing this work and their valuable feedback.\n\n## **Questions**\n\n### **Question 1** - What are the contemporary neural or non-kernel approaches or distribution compression? How does your method perform in comparison?\n\n**The main contribution of this paper are the algorithms (ACKIP, ACKH) which compress the conditional distribution. We are not aware of any other algorithms in the literature that do this, kernel-based or otherwise**. To provide a baseline comparison, we modify Kernel Herding (KH) [R1] to target the joint distribution (JKH), and introduce a joint distribution compression algorithm (JKIP). We show ACKIP achieving superior empirical performance versus these baselines.\n\nIn *non-conditional*, *non-joint* distribution compression, the most popular algorithms are KH [R1], Kernel Thinning (KT) [R2], Support Points (SP) [R3], and gradient flow methods (GF) [R6]. Here we adapt the approach of KH/SP/GF where the compressed set is a free parameter. In KT they restrict themselves to points that already exist in the target dataset. KH, KT and GF are kernel-based, targeting the MMD, whereas SP is an *energy distance (ED)* based method, defined as\n\n\\begin{align*}\nED(\\mathbb{P}_X, \\mathbb{Q}_X) := 2\\mathbb{E}[\\Vert a - b \\Vert] - \\mathbb{E}[\\Vert a - a^\\prime \\Vert] + \\mathbb{E}[\\Vert b - b^\\prime \\Vert]\\\n\\end{align*}\n\nwhere $a, a^\\prime \\sim \\mathbb{P}_X$, $b,b^\\prime \\sim \\mathbb{Q}_X$, and $\\Vert \\cdot \\Vert$ is the 2-norm. The ED is zero iff $\\mathbb{P}_X =\\mathbb{Q}_X$ (Theorem 1, [R3]). While SP does not initially appear to be kernel-based, the energy distance is equivalent to the MMD for a choice of negative-definite kernel function [R4]. \n\n**The existing distribution compression methods are kernel-based. We are not aware of any conditional distribution compression approach, neural-based or otherwise.**\n\n### **Question 2.1** - Are there any kernel preferences specific to the task in question?\n\nAs stated in Theorem 4.1, the **kernel $l$ must be characteristic** [R1], this includes common choices such as the Gaussian and IMQ kernels. This property guarantees that zero AMCMD implies equality of the underlying conditional distributions.\n\nIn our experiments, we use the Gaussian kernel, as it is a universally standard choice in the kernel embedding literature, and in kernel-based methods more broadly. However, we emphasise that our algorithms are **kernel-agnostic**: *any* feature kernel $k$ and *any characteristic* response kernel $l$ can be used, provided their gradients are computable. \n\n### **Question 2.2** -  Why have not you tried other kernels?\n\nAs with any kernel method, the optimal kernel choice is unknown and problem-specific, hence it should be selected with care by the practitioner to align with their inductive biases, see for example [R5]. We have used the Gaussian kernel as it is a *very common* default choice due to its ability to capture smooth similarities. \n\nThe below table includes **new results** on the *Heteroscedastic* data using the **IMQ kernel** for $k$ and $l$. We report the 25th, 50th and 75th percentiles, with ACKIP retaining the best performance in terms of AMCMD and RMSE. \n\n|Method|AMCMD\n|-|-|\n|||\n|JKH|0.0349, 0.0422, 0.0502|\n|JKIP|0.0168, 0.0215, 0.0259|\n|ACKH|0.00443, 0.00697, 0.0191|\n|**ACKIP**| **0.00143, 0.00154, 0.00170**|\n|Random|0.0182, 0.0240, , 0.0336|\n\n| Method | **RMSE**||||\n|-|-|-|-|-|\n||$h(y) = y$|$h(y) =\\sin(y)$|$h(y) =\\exp(-y^2)$|$h(y) =1_{\\{y < 0\\}}$|\n|JKH|0.206, 0.229, 0.266|0.161, 0.170, 0.200| 0.0913, 0.104, 0.115|0.136, 0.168, 0.205|\n|JKIP|0.127, 0.144, 0.218|0.156, 0.157, 0.219| 0.0887, 0.0899, 0.111|**0.116, 0.129**, 0.231|\n|ACKH|0.0892, 0.113, 0.192|0.143, 0.148, 0.150| 0.0882, 0.0918, 0.0988|0.132, 0.144, 0.150|\n|ACKIP|**0.0596, 0.0602, 0.0615**| **0.136, 0.137, 0.138**| **0.0874, 0.0878, 0.0886**|0.127, 0.134, **0.146**|\n|Random|0.134, 0.158, 0.199|0.158,  0.171, 0.193|0.102, 0.114, 0.131|0.138, 0.156, 0.187|\n\nDue to reviewer guidelines we cannot include figures, but **in the final version we will include plots of these new results**.\n\n### **Question 3.1** - How does your method scale with dimensionality (in theory)?\n\nThe below table shows the time and space complexity for each of the methods introduced in this work, assuming the feature space is $d$-dimensional, the response space is $p$-dimensional, the target dataset has size $n$, and the compressed set is size $m$:\n\n| Algorithm | Time Complexity                                   | Memory Complexity                      |\n|-----------|--------------------------------------------------|----------------------------------------|\n| JKH       | $O((m^2 + mn)(d+p))$                             | $O((m + n)(d+p))$                      |\n| JKIP      | $O((m^2 + mn)(d+p))$                             | $O((m^2 + mn)(d+p))$                   |\n| ACKH      | $O(m^4 + m^3n + (m + n)(d+p))$                   | $O((m + n)(d+p) + mn + m^2)$           |\n| ACKIP     | $O(m^3 + m^2n + (m^2 + mn)(d+p))$                | $O((m^2 + mn)(d+p))$   \n\nOne should notice that the **dependence on** $n$ **and** $d, p$ **is never more than $O(nm(d+p))$** for any of the methods in this work, which is quite favourable. **We will include this discussion in the final version**.\n\n### **Question 3.2** - How does your method scale with dimensionality (in practice)?\nOur experiments cover datasets across a large range of dimensions. In the appendix we performed an experiment on mnIST data, which has **moderately high dimension of 784**. In particular, Figures 25 and 26 show that ACKIP achieves very similar classification accuracy to the full data, after 97\\% compression. \n\n## **Weaknesses**\n\n### **Weakness 1.1** - The background review focuses exclusively on kernel methods ... \n\nWe have seen in the answer to Question 1 that **there are no existing approaches to conditional distribution compression in the literature, kernel-based or otherwise**. Moreover, the existing standard distribution compression approaches of which we are aware are kernel-based [R1, R2, R3]. **We will make this clearer in the final version**.\n\n### **Weakness 1.2** - The experimental comparison similarly fails to include non-kernel baselines, limiting the perspective on the method's relative advantages.\n\nWe have tried to provide reasonable baselines, extending existing methods (KH, GF  [R1], [R6]) to target the joint distribution, and by providing metrics based on uniform random subsamples. **We are not aware of any other conditional distribution compression approach which we can compare against**.\n\n### **Weakness 2** - While distribution compression has critical applications in ... the evaluation is conducted primarily in low-dimensional settings. The authors use only one real-world dataset and notably avoid addressing their method's scalability with increasing dimensionality.\n\nWe have seen in the answer to Question 3 that **the appendix contains results for an additional real world data experiment based on mnIST, which has moderately high dimension of 784**. We have also presented a **table showing linear scaling in terms of memory and time complexity with respect to both the dimension of the feature and response space**. \n\nIt is widely known that, like many other methods, kernel methods suffer from the curse of dimensionality, and so we would not expect, and do not claim, to have strong performance on data such as those involved in NLP where dimensionality can be much much higher. **We will make this point clearer in the final version**.\n\n### **Weakness 3** - The analysis concentrates on AMCMD and RMSE for test function expectation approximations, while downstream task performance (e.g., regression/classification accuracy using compressed data for training ML models) would provide more practical insight. This omission leaves the method's real-world utility unclear.\n\n**The reviewer may not have noticed that the empirical results presented in the paper do indeed correspond to regression and classification accuracy.**\n\nTo see this, note that the kernel conditional mean embedding (KCME) can be directly used as a regression or classification model. In particular we point the reviewers attention to Figure 4. When the test function $h(y)$ is chosen such that $h(y) = y$, the KCME is directly approximating the conditional expectation $\\mathbb{E}[Y|X]$, which **is the object of interest in regression**. Moreover, for the setting of multi-class classification, in Figure 8 we report performance for test functions $h(y) = 1_{y=i}$, $i = 1, 2, 3, 4$. In this case we have that \n\\begin{align*}\n        \\mathbb{E}[1_{Y = i} \\mid X] = \\mathbb{P}(Y = i \\mid X),\n\\end{align*}\nand hence Figure 8 reports the error in estimating the class conditional probability, which is the **object of interest in classification**. In Figure 20, we further report the classification accuracy and F1 score. \n\n**We will make the connection between the KCME and regression/classification more clear in the final work**.\n\n### **Weakness 4** - The argument for the consistency of the proposed AMCMD assumes that the distributions are equal. However, the original definition emphasizes the use of a different distribution .\n\nCorollary 4.4. is intended to show consistency exactly in the *special case* that $X = X^\\*$. In particular, ACKH and ACKIP are designed for the case when $X = X^*$. **We will make this clearer in the final version**.\n\n## **References**\n[R1] - Yutian Chen et al. “Super-Samples from Kernel Herding”. 2012\n\n[R2] - Raaz Dwivedi and Lester Mackey. \"Kernel Thinning\". 2024\n\n[R3] - Simon Mak and V. Roshan Joseph. \"Support points\". 2018\n\n[R4] - Dino Sejdinovic et al. “Equivalence of distance-based and RKHS-based statistics in hypothesis testing”.\nIn: The Annals of Statistics 41.5. 2013\n\n[R5] - Thomas Hofmann et al. Kernel methods in machine learning. 2007\n\n[R6] - Michael Arbel, Anna Korba, Adil Salim, Arthur Gretton. Maximum Mean Discrepancy Gradient Flow. 2019"}, {"review_id": "3ZvuoveYzt", "reviewer": "Reviewer_YpGJ", "summary": "Existing methods like Kernel Herding (KH) were originally designed to compress unlabelled data distributions, but no prior approach directly compresses the conditional distribution of labelled data. To fill this gap, the paper first introduce Average Maximum Conditional Mean Discrepancy (AMCMD), a metric for comparing conditional distributions, along with a closed-form estimator. Then show that constructing a compressed set targeting AMCMD can be made much more efficient—reducing the cost from O(n³) to O(n). Based on this insight, we extend KH and propose Average Conditional Kernel Herding (ACKH), a linear-time greedy algorithm for compressing conditional distributions.\n\nTo compare with joint distribution compression, the paper also introduce Joint Kernel Herding (JKH), a straightforward extension of KH for joint data. While herding methods are simple and interpretable, they rely on greedy heuristics. \n\nTo explore better alternatives, the paper  propose Joint Kernel Inducing Points (JKIP) and Average Conditional Kernel Inducing Points (ACKIP)—which jointly optimize the compressed set while still maintaining linear complexity.", "questions": "see weakness.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The paper extends existing kernel compression techniques to the conditional distribution setting and proposes a linear-time optimization approach based on gradient descent. I did not identify any major issues regarding the correctness of the method.\n2. Experimental results under various data distribution settings demonstrate that the proposed method consistently achieves lower RMSE.\n\nWeaknesses: \n1. Writing and Structure:\nThe writing of the paper needs improvement. While several method variants are introduced, including some mentioned in the abstract, it is difficult to follow the key logical connections between them. The discussion of related work is insufficient in the main text; although some references are included in the appendix, this weakens the overall motivation of the paper. For example, it is unclear why existing methods perform poorly and why compressing the joint distribution is less effective than compressing the conditional distribution. I recommend adding a dedicated section to clearly outline the main contributions and structure of the paper. In addition, many important details require flipping back and forth between the main text and the appendix, which disrupts the flow of reading.\n\n2. Theoretical Contribution:\nThe theoretical novelty is relatively weak. The proposed criteria are derived based on well-studied conditional kernel mean embedding estimators, and the derivation mainly relies on direct computation. The paper lacks convergence analysis or sample error bounds, which are essential for establishing the robustness of the method.\n\n3. Experimental Evaluation:\nThe experimental section lacks clarity in dataset presentation. For example, in line 255, one dataset is briefly mentioned without any description of its features or relevance. Additionally, the meaning of the x-axis in the figures is not explained, making the visualizations less informative.\n\n4. Experimental Limitations:\nMost experiments rely on the Gaussian kernel and are conducted on relatively low-dimensional variables, which may limit the generality of the conclusions. Furthermore, the evaluation metric is solely based on RMSE. While RMSE is appropriate for regression tasks, the goal of distribution compression is often to support downstream tasks more broadly. Therefore, including results on a wider range of downstream applications would make the evaluation more convincing and practical.\n\nminor: A few minor points:\n1. The notation for the separable measure space in lines 85 and 86 is inconsistent.\n2. Why is it m+1​ in Equation (2) instead of m?\n3. In line 219, two matrix dimensions appear to be inconsistent.\n4. line 248: Figures 2 and3 ->Figures 2 and 3", "was_revised": true, "final_justification": "The authors have addressed most of my concerns during the rebuttal period. I have decided to raise my score from 3 to 4, given that the method have been successfully extended existing tools to a new application in the conditional distribution setting.", "rebuttal": "We thank the reviewer for the time and effort dedicated to reviewing this work and for their valuable feedback. In particular, we appreciate the constructive comments on the paper’s writing and structure. \n\n## **Weaknesses**\n\n### **Weakness 1.1** - The writing of the paper needs improvement. While several method variants are introduced ... it is difficult to follow the key logical connections between them. I recommend adding a dedicated section to outline the main contributions and structure of the paper.\n\n**In the introduction, we provide bullet points outlining the main contributions of the paper. We recognise, however, that introducing four distinct algorithms may make it difficult to see their logical connections.** \n\nThe central goal of our work is to compress the conditional distribution, for which no current approach is available. To this end, we extend Kernel Herding (KH)—originally designed for marginal distributions—to the conditional setting, resulting in **ACKH**. To provide a fair baseline comparison, we also extend KH to target the joint distribution, yielding **JKH**.\n\nKH relies on a greedy, point-by-point selection heuristic, which can produce suboptimal solutions. To address this limitation, we introduce **ACKIP** and **JKIP**, which target the conditional and joint distributions respectively, but **optimise all points in the compressed set jointly rather than greedily**. Our experiments show that this leads to improved performance.\n        \n**We will revise the introduction in the final version to make these connections and contributions clearer to the reader.**\n\n### **Weakness 1.2** - The discussion of related work is insufficient in the main text; although some references are included in the appendix, this weakens the overall motivation of the paper.\n\nWe agree that additional discussion of related work in the main text will strengthen the motivation of the paper. Unfortunately, space constraints meant this section was moved to the appendix. **We will include a related work section in the main body of the final paper with the additional space provided.**\n\n### **Weakness 1.3** - It is unclear why existing methods perform poorly and why compressing the joint distribution is less effective than compressing the conditional distribution. \n\n**We stress that there are no existing methods that perform conditional distribution compression**, this work is the first to develop a conditional distribution compression procedure. \n\nIn order to get an **inutitive sense** for why compressing the conditional distribution directly, rather than as a by-product of joint distribution compression is preferred, it may be helpful to make an **analogy to conditional density estimation**. The naive method for estimating conditional densities $p(y | x)$  is to first estimate the joint $p(x, y)$ and marginal $p(x)$ densities, then set\n$$\n \\hat{p}(y | x) := \\frac{\\hat{p}(x, y)}{\\hat{p}(x)},\n$$\nhowever this approach is error propagating. It has been shown that stronger empirical performance is found when *directly* estimating the conditional density, see for example [R3]. Similarly, our empirical results suggest it is better to compress the conditional distribution directly.\n\nMoreover, JKH/JKIP and ACKH/ACKIP optimise different loss functions designed for different tasks, so it is unsurprising that compressing via AMCMD (ACKH, ACKIP) outperforms JMMD (JKH, JKIP) empirically.\n\n**We will include discussion around this in the introduction of the work to improve clarity.**\n\n### **Weakness 2** - The theoretical novelty is relatively weak. The proposed criteria are derived based on well-studied conditional kernel mean embedding estimators ... The paper lacks convergence analysis or sample error bounds, which are essential for establishing the robustness of the method.\n\nWhile our proposed criteria build on the well-studied framework of kernel conditional mean embeddings, **the novelty lies in their adaptation to the problem of conditional distribution compression, which has not been addressed previously**. While convergence rates and sample error bounds are important, they are not our main interest, which is instead to establish the feasibility and practical benefit of conditional distribution compression. Our focus in this work is on algorithmic formulation and empirical validation, rather than asymptotic analysis. \n\n**Our extensive empirical analysis demonstrates that the proposed algorithms are robust**, consistently delivering strong performance across a diverse range of datasets—both synthetic and real—and in both regression and classification settings. Importantly, given any random sample, our algorithms can be initialised with that sample and, with standard gradient descent tuning, produce a set that achieves a lower AMCMD.\n\n### **Weakness 3** - The experimental section lacks clarity in dataset presentation. For example, in line 255, one dataset is briefly mentioned without any description of its features or relevance. Additionally, the meaning of the x-axis in the figures is not explained, making the visualizations less informative.\n\n**We respectfully clarify that this is a misunderstanding.** Line 255 only introduces Section 5.2; for all datasets used, we consistently describe their features and explain their relevance in the main text before pointing to figures presenting results. See for example Section 5.2.1. \n\nThe figure at the top of page 7 is related to the *Superconductivity* dataset, which may have caused confusion. To avoid any possible ambiguity, **we will revise the layout and figure captions in the final version to make these associations between datasets, descriptions, and figures clearer**. \n\n**Additionally, we thank the reviewer for pointing out that the x-axis of some figures are unlabelled, we will rectify this in the final version.**\n\n### **Weakness 4.1** - Most experiments rely on the Gaussian kernel ...\n\nIn our experiments, we use the Gaussian kernel, as it is a universally standard choice in the kernel embedding literature [R1 , R2], and in kernel-based methods more broadly [R4]. **However, we emphasise that our algorithms are kernel-agnostic**: *any* feature kernel $k$ and *any characteristic* response kernel $l$ can be used, provided their gradients are computable. \n\nThe below table includes **new results** on the *Heteroscedastic* data using the **IMQ kernel** for $k$ and $l$. We report the 25th, 50th and 75th percentiles, with ACKIP retaining the best performance in terms of AMCMD and RMSE. \n\n|Method|AMCMD\n|-|-|\n|||\n|JKH|0.0349, 0.0422, 0.0502|\n|JKIP|0.0168, 0.0215, 0.0259|\n|ACKH|0.00443, 0.00697, 0.0191|\n|**ACKIP**| **0.00143, 0.00154, 0.00170**|\n|Random|0.0182, 0.0240, , 0.0336|\n\n| Method | **RMSE**||||\n|-|-|-|-|-|\n||$h(y) = y$|$h(y) =\\sin(y)$|$h(y) =\\exp(-y^2)$|$h(y) =1_{\\{y < 0\\}}$|\n|JKH|0.206, 0.229, 0.266|0.161, 0.170, 0.200| 0.0913, 0.104, 0.115|0.136, 0.168, 0.205|\n|JKIP|0.127, 0.144, 0.218|0.156, 0.157, 0.219| 0.0887, 0.0899, 0.111|**0.116, 0.129**, 0.231|\n|ACKH|0.0892, 0.113, 0.192|0.143, 0.148, 0.150| 0.0882, 0.0918, 0.0988|0.132, 0.144, 0.150|\n|ACKIP|**0.0596, 0.0602, 0.0615**| **0.136, 0.137, 0.138**| **0.0874, 0.0878, 0.0886**|0.127, 0.134, **0.146**|\n|Random|0.134, 0.158, 0.199|0.158,  0.171, 0.193|0.102, 0.114, 0.131|0.138, 0.156, 0.187|\n\nDue to reviewer guidelines we cannot include figures, but **in the final version we will include plots of these new results**.\n\n### **Weakness 4.2** - Most experiments ... are conducted on relatively low-dimensional variables, which may limit the generality of the conclusions.\n\nOur experiments cover datasets across a large range of dimensions. In the appendix we performed an experiment on mnIST data, which has **moderately high dimension of 784**. In particular, Figures 25 and 26 show that ACKIP achieves very similar classification accuracy to the full data, after 97\\% compression. \n\n### **Weakness 4.3** - The evaluation metric is solely based on RMSE. While RMSE is appropriate for regression tasks, the goal of distribution compression is often to support downstream tasks more broadly.\n\nWe respectfully disagree with the comments on downstream tasks. \n\nThe KCME has many valuable downstream applications, as discussed in the introduction. **However, crucially, these all rely on the KCME’s ability to approximate conditional expectations of functions of random variables. Our empirical results demonstrate that this capability is preserved under compression**, with the RMSE being a natural choice of error metric. These results suggests strong downstream performance in other applications.\n\n**Moreover, the empirical results presented in the paper cover both regression and classification as downstream tasks.** To see this, note that the kernel conditional mean embedding (KCME) can be directly used as a regression or classification model. In particular we point the reviewers attention to Figure 4. When the test function $h(y)$ is chosen such that $h(y) = y$, the KCME estimates $\\mathbb{E}[Y|X]$, which **is the object of interest in regression**. Moreover, for multi-class classification, in Figure 8 we report performance for test functions $h(y) = 1_{y=i}$, $i = 1, 2, 3, 4$. In this case we have that \n$$\n        \\mathbb{E}[1_{Y = i} | X] = \\mathbb{P}(Y = i | X),\n$$\nand hence Figure 8 reports the error in estimating the class conditional probability, which is the **object of interest in classification**. In Figure 20, we also report the classification accuracy and F1 score achieved by each of the methods, with ACKIP achieving parity with the full data after 97% compression. \n\n## **References**\n\n[R1] - Yutian Chen et al. “Super-Samples from Kernel Herding”. 2012\n\n[R2] - Raaz Dwivedi and Lester Mackey. \"Kernel Thinning\". 2024\n\n[R3] - Rafael Izbicki and Ann B. Lee. “Nonparametric Conditional Density Estimation in a High-Dimensional Regression Setting”. 206.\n\n[R4] - Thomas Hofmann et al. Kernel methods in machine learning. 2007"}, {"review_id": "do6mMaL90n", "reviewer": "Reviewer_r3Jq", "summary": "This paper addresses conditional distribution compression for labeled data, a problem distinct from existing joint distribution compression approaches. The authors introduce the Average Maximum Conditional Mean Discrepancy (AMCMD) as a novel metric for comparing families of conditional distributions, proving it satisfies standard metric properties (triangle inequality, identity of indiscernibles). Leveraging this metric, they propose two algorithms: (1) Average Conditional Kernel Herding (ACKH), a greedy linear-time algorithm, and (2) Average Conditional Kernel Inducing Points (ACKIP), a joint optimization alternative. For comparison, they also develop joint distribution compression methods: Joint Kernel Herding (JKH) and Joint Kernel Inducing Points (JKIP). A key theoretical contribution is reducing AMCMD estimation complexity from O(n³) to O(n) via the tower property (Lemma 4.7). Experiments across synthetic and real datasets demonstrate that (1) conditional compression outperforms joint compression, and (2) joint optimization consistently outperforms greedy approaches, with ACKIP achieving near full-data performance using only 3% of the original dataset.", "questions": "- Since JKH and JKIP both have the same complexity of O(mn + m^2), do you observe any empirical speed difference between the two? Is there any scenario that the greedy one is preferred?\n- Is there a mistake in equation (2) - should be $k(x, \\tilde{x_j})l(y, \\tilde{y}_j)$ instead of $k(x, \\tilde{x_j})k(y, \\tilde{y}_j)$", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### Strength\n\n- The paper has considered both the joint and conditional kernel herding and uses experiments to prove the effectiveness of doing conditional distribution compression, rather than the joint one.\n- This paper is the first direct approach to conditional distribution compression, addressing a genuine gap in the literature where existing methods compress joint distributions and hope conditional structure is preserved.\n- The paper presents a clear logical progression, going from joint to conditional and from greedy to the joint optimization.\n- The paper also addresses a computational bottleneck of estimating AMCMD from O(n^3) to O(n).\n- Demonstrates substantial compression ratios (97% data reduction) while maintaining statistical performance, with potential to significantly expand KCME applicability.\n\n### Weakness\n\n- The experiments are a bit weak in terms of the downstream tasks or practical guidance. For example, the Kernel Herding paper[3]’s experiments setting that this paper claims to follow also includes the Bayesian Posterior.\n- Experiments also lack the comparison to other baseline methods.\n- The paper claims AMCMD is \"more general\" than existing metrics (KCD/AMMD) but provides no compelling use cases requiring this generality\n- The writing of the paper requires substantial work. There is dense notation in Section 4 with insufficient motivation for theoretical developments\n- Memory constraints limit mnIST to 10K samples, reducing confidence in large-scale applicability", "was_revised": true, "final_justification": "The authors have addressed most of my concerns during the rebuttal period. Although I still have some concerns about the general applicability of the method, I have decided to raise my score from 3 to 4 given the technical soundness and the potential of this method.", "rebuttal": "We thank the reviewer for the time and effort dedicated to reviewing this work and for their valuable feedback. In particular we appreciate the reviewer pointing out the lack of clarity in our argument for the increased generality offered by AMCMD.\n\n## **Weaknesses**\n\n### **Weakness 1** - The experiments are a bit weak in terms of the downstream tasks or practical guidance...\n\nWe respectfully disagree with the comments on downstream tasks. \n\nThe KCME has many valuable downstream applications, as discussed in the introduction. **However, crucially, these all rely on the KCME’s ability to approximate conditional expectations of functions of random variables. Our empirical results demonstrate that this capability is preserved under compression**, with the RMSE being a natural choice of error metric. These results suggests strong downstream performance in other applications.\n\n**Moreover, the empirical results presented in the paper cover both regression and classification as downstream tasks.** To see this, note that the kernel conditional mean embedding (KCME) can be directly used as a regression or classification model. In particular we point the reviewers attention to Figure 4. When the test function $h(y)$ is chosen such that $h(y) = y$, the KCME estimates $\\mathbb{E}[Y|X]$, which **is the object of interest in regression**. Moreover, for multi-class classification, in Figure 8 we report performance for test functions $h(y) = 1_{y=i}$, $i = 1, 2, 3, 4$. In this case we have that \n$$\n        \\mathbb{E}[1_{Y = i} | X] = \\mathbb{P}(Y = i | X),\n$$\nand hence Figure 8 reports the error in estimating the class conditional probability, which is the **object of interest in classification**. In Figure 20, we also report the classification accuracy and F1 score achieved by each of the methods, with ACKIP achieving parity with the full data after 97% compression. \n\n### **Weakness 2** - Experiments also lack the comparison to other baseline methods.\n\n**The main contribution of this paper are the algorithms (ACKIP, ACKH) which compress the conditional distribution. We are not aware of any other algorithms in the literature that do this, kernel-based or otherwise**. To provide a baseline comparison, we modify Kernel Herding (KH) [R1] to target the joint distribution (JKH), and introduce a gradient flow based [R4] joint distribution compression algorithm (JKIP). We also provide comparison to uniform random subsampling which is used frequently throughout the standard distribution compression literature [R1, R2]. We show ACKIP achieving superior empirical performance versus these baselines.\n\n### **Weakness 3** - The paper claims AMCMD is \"more general\" than existing metrics (KCD/AMMD) but provides no compelling use cases requiring this generality.\n\nIn the main body of the text we point towards Section C.2 in the appendix which includes an experiment illustrating the inflexibility of the KCD/AMMD compared to the AMCMD. Specifically, **the KCD/AMMD fails to detect similarity in the conditional distributions of two datasets within particular regions of the conditioning space, only detecting global similarity.** This stems from its requirement that both the distribution of the conditioning variable and the expectation measure be identical, making it unsuitable for such scenarios. \n\n**We agree that this was not obvious in the original paper as we did not have space to expand upon this. With additional space we will rectify this in the final version.**\n\n**Moreover, in Section A.4. we expand upon the possible use cases of the AMCMD that are out of scope for the work in this paper. These applications include the widely studied areas of Covariate and Conditional Shift, which would not be possible using the KCD/AMMD. We will include further discussion on this topic in the main body for the final version.**\n\n### **Weakness 4** - The writing of the paper requires substantial work. There is dense notation in Section 4 with insufficient motivation for theoretical developments.\n\nWe appreciate the reviewer’s feedback regarding the clarity of Section 4. We acknowledge that this section is notation-heavy due to the mathematical nature of our theoretical contributions. However, the notation we have used throughout the section is standard in the KCME [R3] and distribution compression literature [R1, R2]. \n\n### **Weakness 5** - Memory constraints limit mnIST to 10K samples, reducing confidence in large-scale applicability.\n\nThe below table shows the memory complexity for each of the methods introduced in this work, assuming the feature space is $d$-dimensional, the response space is $p$-dimensional, the target dataset has size $n$, and the compressed set is size $m$:\n\n| Algorithm | Memory Complexity |\n|-----------|--------------------------------------------------|\n| JKH      | $O((m + n)(d+p))$|\n| JKIP      | $O((m^2 + mn)(d+p))$|\n| ACKH      | $O((m + n)(d+p) + mn + m^2)$ |\n| ACKIP     | $O((m^2 + mn)(d+p))$   \n\nOne should notice that the **dependence on** $n$ **and** $d, p$ **is never more than $O(nm(d+p))$** for any of the methods in this work, which is quite favourable. **We will include this discussion in the final version**.\n\n**We restrict the size of the data to 10K samples due to a lack of access to GPUs with high VRAM; the experiments were run locally with just 12GB of VRAM. However we have seen above that the dependence upon dimensionality is linear, and so this could be easily expanded with access to more compute.**\n\n## **Questions**\n\n### **Question 1** - Since JKH and JKIP both have the same complexity of $O(mn + m^2)$, do you observe any empirical speed difference between the two? Is there any scenario that the greedy one is preferred?\n\nDue to reviewer guidelines, we cannot include figures in this discussion, however the below table shows the wall clock time for constructing a compressed set of size $m = 250$  targeting $n = 8000$ datapoints for each of the methods introduced in this work. **We will include a figure showing size of compressed set versus wall clock time in the final version of the paper.**\n\nWe report the 25th, 50th and 75th percentiles over 20 runs, the results shows that **JKIP is faster than JKH in practice**, and **ACKIP is much faster than ACKH in practice**.\n\n|Method|Wall Clock Time (s)\n|-|-|\n|||\n|JKH|8.671, 8.729, 8.996|\n|**JKIP**|**0.8476, 0.8731, 0.8773**|\n|ACKH|294.4, 300.2, 345.8|\n|**ACKIP**| **11.40, 11.42, 11.45**|\n\nThe reason for JKIP being faster than JKH is fairly techincal. As noted in the appendix, the algorithms in this paper were implemented using JAX. JAX enables Just-In-Time (JIT) compilation, which significantly increases execution speed. However, to achieve this speed, JAX relies on an immutable array structure, meaning the arrays must not change shape during program execution. As a result, JKH and ACKH cannot fully leverage the speed benefits of JIT compilation, as the size of the compressed set, and hence the corresponding arrays, increases at every iteration. Conversely, the arrays considered in JKIP and ACKIP stay the same shape throughout. This presents a notable practical advantage of JKIP and ACKIP over JKH and ACKH.\n\n**JKH could, in principle, be faster than JKIP if optimising each individual pair requires far fewer iterations than optimising the entire compressed set jointly. However, this was not observed in any of our experiments.**\n\n### **Question 2** - Is there a mistake in equation (2)...\n\nYes, thank you for pointing this out, we will fix this in the final version.\n\n## **References**\n\n[R1] - Yutian Chen et al. “Super-Samples from Kernel Herding”. 2012\n\n[R2] - Raaz Dwivedi and Lester Mackey. \"Kernel Thinning\". 2024\n\n[R3] - Junhyung Park, Krikamol Muandet. A Measure-Theoretic Approach to Kernel Conditional Mean Embeddings. 2020\n\n[R4] - Michael Arbel, Anna Korba, Adil Salim, Arthur Gretton. Maximum Mean Discrepancy Gradient Flow. 2019"}, {"review_id": "QYvIxg7CNc", "reviewer": "Reviewer_ris1", "summary": "This paper studies the problem of compressing labeled data while preserving the properties of the original distribution. The authors extend concepts in Kernel Herding, which is used for compressing unlabeled data. They also consider joint distribution where they first extend Kernel Herding to Joint Kernel Herding (JKH) and also develop a new algorithm called Joint Kernel Inducing Points (JKIP). They introduce a new metric called Average Maximum Conditional Mean Discrepancy (AMCMD) and derive a closed-form formula for it. They extend the Kernel Herding algorithm to Average Conditional Kernel Herding (ACKH). They also develop a new algorithm called Average Conditional Inducing Points (ACKIP) which, instead of sequentially constructing the compression set, works with sets of points and iteratively updates the set via gradient descent. The point-based algorithm move away from greedy optimization that sequentially constructs a set and they turn out to be more efficient. The proposed algorithms are evaluated through comprehensive set of experiments.", "questions": "- Why are they 20 points (instead of 25) in the Figure 1 for ACKIP, do we have points that are repeated? \n- Why do the point-based algorithm converge? what is their convergence time? Also what is the effect of initialization step in these methods? \n- What is the runtime of the algorithms? Can you add plots or simply report the runtime? \n- Are they non-Kernel methods are used for compression? how do they perform? How do they compare to the proposed algorithms?", "limitations": "yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strength: \n- paper studies a fundamental problem which has been considered before and so many of the properties have been explored before however they gather all these findings from various resources and present a comprehensive study of previous work. \n- Introduction of new way of measuring the discrepancy between original and compressed distribution. Showing that it is metric and providing a closed-formula for it. \n- Proposing new algorithms with better runtime and measuring their performance in practice. \n- Strong empirical evidence of superiority of the proposed algorithms. \n\nWeakness: \n-  There are no discussion in terms of convergence of the point-based methods? Similarly for initialization, they mention uniform sampling but no other discussion. \n- Samples that are necessarily a part of the original training set  but appear in compression set are not thoroughly discussed, e.g., what is conditional property for these samples? how are they handled generally?\n\n\nMinor: \n- Typo Eq(2) l(y,.) instead of k(y,.) in the sum. \n- l248 add space", "was_revised": true, "final_justification": "This is a solid result with comprehensive experiment set. Authors resolved my concern about comparison with non-kernel based methods. My final recommendation is accept.", "rebuttal": "We thank the reviewer for their positive and thoughtful feedback, and we understand their cautious confidence score. To clarify, our work focuses on **conditional distribution compression, a problem which, to the best of our knowledge, has not been studied before.** We hope the additional clarifications provided here help strengthen the reviewer’s confidence in their understanding of the contributions and novelty of our work.\n\n## **Weaknesses**\n\n### **Weakness 1.1** - There are no discussion in terms of convergence of the point-based methods? \n\nWe thank the reviewer for raising this important point. While convergence rates and sample error bounds are important, they are not our main interest, which is instead to, for the first time, establish the feasibility and practical benefit of conditional distribution compression. Our focus in this work is on algorithmic formulation and empirical validation, rather than asymptotic analysis. In particular, **the novelty lies in the adaptation to the problem of conditional distribution compression, which has not been addressed previously**.\n\n**Our extensive empirical analysis demonstrates that the proposed algorithms are robust**, consistently delivering strong performance across a diverse range of datasets—both synthetic and real—and in both regression and classification settings. Importantly, given any random sample, our algorithms can be initialised with that sample and, with standard gradient descent tuning, produce a set that achieves a lower AMCMD.\n\n### **Weakness 1.2** - Similarly for initialization, they mention uniform sampling but no other discussion.\n\nRegarding initialisation, while uniform sampling is a natural and widely used choice in distribution compression (e.g., Kernel Herding, Support Points [R1, R2]), we agree that alternative initialisation strategies could be explored. **We will include a brief discussion in the revision highlighting that initialisation is flexible**, and more sophisticated methods can be readily incorporated into our framework. However, we note that the **provided results are given with accompanying 25th and 75th percentiles which suggest that the performance of the algorithm is stable with respect to the choice of random initialisation.**\n\n### **Weakness 2** - Samples that are necessarily a part of the original training set but appear in compression set are not thoroughly discussed, e.g., what is conditional property for these samples? how are they handled generally?\n\nWe appreciate the reviewer highlighting this technical point. The compressed sets produced by our algorithms are the result of gradient-based optimisation, where the compressed set is treated as a parameter and optimised directly with respect to the AMCMD/JMMD objectives. As a result, it is **extremely unlikely that points from the original training set would be selected verbatim for the compressed set**.\n\nNevertheless, the kernel conditional mean embedding is well defined for any choice of $\\boldsymbol{x} \\in \\mathcal{X}$, $\\boldsymbol{y} \\in \\mathcal{Y}$, even those in the set used to train it, and hence **if training points did appear in the compressed set there would be no issue.** For further discussion on the properties of the kernel conditional mean embedding, see [R3].\n\n### **Minor Points** \nWe thank the reviewer for pointing out these typos.\n\n## **Questions**\n\n### **Question 1** - Why are they 20 points (instead of 25) in the Figure 1 for ACKIP, do we have points that are repeated?\n\nWe thank the reviewer for catching this, as it raises an interesting technical point. In Figure 1, some points have been optimised such that they appear to overlap visually. However, they are not identical; rather, they lie close together in the data space and only appear to coincide due to the marker size used in the plot.\n\nThis clustering of points can be interpreted as a form of weighting, indicating that certain regions of the data space are particularly important for conditional distribution compression. As a result, these regions are represented more heavily in the compressed set—something that may not be captured by random sampling.\n\n### **Question 2.1** - Why do the point-based algorithm converge? \n\nOur algorithms optimise differentiable loss functions (e.g., AMCMD, JMMD) and therefore inherit the well-established convergence behaviour of gradient-based optimisation. In practice, we observed that the algorithms required minimal hyperparameter tuning to achieve convergence. Furthermore, our empirical analysis shows that the proposed methods are robust, consistently converging across a wide range of datasets—both synthetic and real—and in both regression and classification tasks.\n\n### **Question 2.2** - What is their convergence time?\n\nIn practice, we observe rapid convergence, often within a small number of iterations, as shown in our experimental results where the loss stabilises quickly across datasets. Providing theoretical convergence rates may be possible for specific kernels, and choice of generating distribution, but is beyond the scope of this paper. \n\n### **Question 2.3** - Also what is the effect of initialization step in these methods?\n\nWe use uniform random sampling as a simple and widely adopted starting point (e.g., kernel herding [R1]). Our empirical results show that even with this simple initialisation, the algorithm consistently outperforms the initial random sample, demonstrating robustness. We note that alternative initialisations (e.g., Gaussian initialisation, data-dependent seeding) can be easily incorporated and may further improve convergence speed, which we will briefly discuss in the revised paper.\n\n### **Question 3** - What is the runtime of the algorithms? Can you add plots or simply report the runtime?\n\nThe time complexity of the algorithms developed in this work is summarised in the following table which we will include in the final version:\n\n| Algorithm | Time Complexity  |\n|-----------|--------------------------------------------------|\n| JKH       | $O((m^2 + mn)(d+p))$                             | \n| JKIP      | $O((m^2 + mn)(d+p))$                             |\n| ACKH      | $O(m^4 + m^3n + (m + n)(d+p))$                   | \n| ACKIP     | $O(m^3 + m^2n + (m^2 + mn)(d+p))$                |\n\nDue to reviewer guidelines, we cannot include figures in this discussion, however the below table shows the wall clock time for constructing a compressed set of size $m = 250$  targeting $n = 8000$ datapoints for each of the methods introduced in this work. **We will include a figure showing size of compressed set versus wall clock time in the final version of the paper.**\n\nWe report the 25th, 50th and 75th percentiles over 20 runs, the results shows that **JKIP is faster than JKH in practice**, and **ACKIP is much faster than ACKH in practice**.\n\n|Method|Wall Clock Time (s)\n|-|-|\n|||\n|JKH|8.671, 8.729, 8.996|\n|**JKIP**|**0.8476, 0.8731, 0.8773**|\n|ACKH|294.4, 300.2, 345.8|\n|**ACKIP**| **11.40, 11.42, 11.45**|\n\nThe reason for JKIP being faster than JKH is fairly techincal. As noted in the appendix, the algorithms in this paper were implemented using JAX. JAX enables Just-In-Time (JIT) compilation, which significantly increases execution speed. However, to achieve this speed, JAX relies on an immutable array structure, meaning the arrays must not change shape during program execution. As a result, JKH and ACKH cannot fully leverage the speed benefits of JIT compilation, as the size of the compressed set, and hence the corresponding arrays, increases at every iteration. Conversely, the arrays considered in JKIP and ACKIP stay the same shape throughout. This presents a notable practical advantage of JKIP and ACKIP over JKH and ACKH.\n\n### **Question 4** - Are they non-Kernel methods are used for compression? how do they perform? How do they compare to the proposed algorithms?\n\n**The main contribution of this paper are the algorithms (ACKIP, ACKH) which compress the conditional distribution. We are not aware of any other algorithms in the literature that do this, kernel-based or otherwise**. To provide a baseline comparison, we modify Kernel Herding (KH) [R1] to target the joint distribution (JKH), and introduce a gradient-flow based [R6] joint distribution compression algorithm (JKIP). We show ACKIP achieving superior empirical performance versus these baselines.\n\nIn *non-conditional* distribution compression, the most popular algorithms are KH [R1], Kernel Thinning (KT) [R2], Support Points (SP) [R4] and gradient flow (GF) based approaches [R6]. Here we adapt the approach of KH/SP/GF where the compressed set is a free parameter. In KT they restrict themselves to points that already exist in the target dataset. KH, KT and GF are both kernel-based, targeting the MMD, whereas SP is an *energy distance (ED)* based method, defined as\n\n\\begin{align*}\nED(\\mathbb{P}_X, \\mathbb{Q}_X) := 2\\mathbb{E}[\\Vert a - b \\Vert] - \\mathbb{E}[\\Vert a - a^\\prime \\Vert] + \\mathbb{E}[\\Vert b - b^\\prime \\Vert]\\\n\\end{align*}\n\nwhere $a, a^\\prime \\sim \\mathbb{P}_X$, $b,b^\\prime \\sim \\mathbb{Q}_X$, and $\\Vert \\cdot \\Vert$ is the 2-norm. The ED is zero iff $\\mathbb{P}_X =\\mathbb{Q}_X$ (Theorem 1, [R5]). While SP does not initially appear to be kernel-based, the energy distance is equivalent to the MMD for a choice of negative-definite kernel function [R5]. \n\n## **References**\n\n[R1] - Yutian Chen et al. “Super-Samples from Kernel Herding”. 2012\n\n[R2] - Raaz Dwivedi and Lester Mackey. \"Kernel Thinning\". 2024\n\n[R3] - Junhyung Park, Krikamol Muandet. A Measure-Theoretic Approach to Kernel Conditional Mean Embeddings. 2020\n\n[R4] - Simon Mak and V. Roshan Joseph. \"Support points\". 2018\n\n[R5] - Dino Sejdinovic et al. “Equivalence of distance-based and RKHS-based statistics in hypothesis testing”. In: The Annals of Statistics 41.5. 2013\n\n[R6] - Michael Arbel, Anna Korba, Adil Salim, Arthur Gretton. Maximum Mean Discrepancy Gradient Flow. 2019"}, {"review_id": "mfRNLL7vvn", "reviewer": "Reviewer_hGvG", "summary": "This paper extends the distribution‐compression problem to the conditional‐distribution setting and proposes a family of kernel metrics and algorithms for selecting the best compression set in an RKHS. Specifically, the authors introduce AMCMD (Average Maximum Conditional Mean Discrepancy), prove it is a valid metric, and show it can be estimated in O(n) time—rather than O(n^3)—by leveraging the tower property.\nBuilding on AMCMD, they present ACKH, a compression algorithm for conditional distributions, and demonstrate experimentally that ACKH outperforms the joint‐distribution approach (JKH). They also propose an inducing‐point variant, ACKIP, which achieves superior performance on both synthetic and real‐world datasets. Overall, the paper is well motivated and clearly written.", "questions": "1. What types of real-world data motivate this approach? In particular, under what practical conditions does ACKH outperform JKH? Clarifying this would better justify focusing on conditional distributions.\n2. Could you clarify in the main text how ACKIP's complexity improves over ACKH --- specifically, why the inducing-point variant is $m$ times faster? \n3. In Eq. (6), you introduced random-variable notations: X*, Y|X, Y'|X'. I understand this is for generality, but could you explain what these distributions represent? For example, is X* the empirical marginal of P(X,Y)?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The method is theoretically sound and intuitive.\n2. The benefit of modeling $P(Y|X)$ directly—rather than via the joint distribution—is clearly demonstrated through experiments.\n3. Empirical results are consistent, and the improvements are substantial.\n4. Computational complexity is carefully addressed, and the algorithms appear practical for real‐world use.\n\nWeaknesses:\n1. The discussion focuses narrowly on kernel herding; positioning this work relative to other distribution‐compression methods would strengthen the paper.\n2. The circumstances under which one should choose ACKH over JKH are shown empirically but lack a more intuitive, conceptual explanation.", "was_revised": true, "final_justification": "I have read the rebuttal and comments of the other reviewers.\nI decide to keep my original score.", "rebuttal": "We thank the reviewer for the time and effort dedicated to reviewing this work and for their positive feedback. In particular, we appreciate the opportunity to clarify the motivation of the work.\n\n## **Weaknesses**\n\n### **Weakness 1** - The discussion focuses narrowly on kernel herding; positioning this work relative to other distribution‐compression methods would strengthen the paper.\n\nWe thank the reviewer for this suggestion.\n\n**The main contribution of this paper are the algorithms (ACKIP, ACKH) which compress the conditional distribution. We are not aware of any other algorithms in the literature that do this, kernel-based or otherwise**. \n\nIn *non-conditional* distribution compression, the most popular algorithms are KH [R1], Kernel Thinning (KT) [R2], Support Points (SP) [R3], and gradient-flow (GF) based methods [R7]. Here we adapt the approach of KH/SP/GF where the compressed set is a free parameter. In KT they instead restrict themselves to points that already exist in the target dataset, as their original motivation was to thin the output of MCMC procedures. KH, KT, and GF are both kernel-based, targeting the MMD, whereas SP is an *energy distance (ED)* based method, where the energy distance is defined as\n\n\\begin{align*}\nED(\\mathbb{P}_X, \\mathbb{Q}_X) := 2\\mathbb{E}[\\Vert a - b \\Vert] - \\mathbb{E}[\\Vert a - a^\\prime \\Vert] + \\mathbb{E}[\\Vert b - b^\\prime \\Vert]\\\n\\end{align*}\n\nwith $a, a^\\prime \\sim \\mathbb{P}_X$, $b,b^\\prime \\sim \\mathbb{Q}_X$, and $\\Vert \\cdot \\Vert$ is the 2-norm. The ED is zero iff $\\mathbb{P}_X =\\mathbb{Q}_X$ (Theorem 1, [R4]). While SP does not initially appear to be kernel-based, the energy distance can be shown to be equivalent to the MMD for a choice of negative-definite kernel function [R4]. Hence the existing non-conditional distribution compression methods can all be thought of as kernel-based.\n\n**We will include this expanded discussion on the existing non-conditional distribution compression methods in the final version.** In particular, we will explicitly compare these methods with our contributions, clarifying their respective scopes and limitations.\n\n### **Weakness 2** - The circumstances under which one should choose ACKH over JKH are shown empirically but lack a more intuitive, conceptual explanation.\n\nWe thank the reviewer for raising this point. In order to understand why compressing the conditional distribution directly, rather than as a by-product of joint distribution compression is more favourable, it may be helpful to make an analogy to conditional density estimation. The naive method for estimating conditional densities $p(y \\mid x)$  is to first estimate the joint $p(x, y)$ and marginal $p(x)$ densities, then set\n\\begin{align*}\n   \\hat{p}(y \\mid x) := \\frac{\\hat{p}(x, y)}{\\hat{p}(x)},\n\\end{align*}\nhowever this approach is error propagating, and it is better to *directly* estimate the object of interest, the conditional density, see for example [R6]. This analogy follows our case quite closely, as our empirical results suggest it is far better to compress the conditional distribution directly, rather than to compress the joint distribution. \n\nMoreover, JKH/JKIP and ACKH/ACKIP optimise different loss functions designed for different tasks, so it is not too surprising that compressing via AMCMD (ACKH, ACKIP) outperforms JMMD (JKH, JKIP) empirically.\n\n**We will include additional intuition in the final version of the paper.**\n\n## **Questions**\n\n### **Question 1** - What types of real-world data motivate this approach? In particular, under what practical conditions does ACKH outperform JKH? Clarifying this would better justify focusing on conditional distributions.\n\nWe thank the reviewer for highlighting the importance of motivating practical use cases.\n\nOur approach is broadly applicable because the kernel conditional mean embedding (KCME) is defined on any space with a positive definite kernel. In this work, we focus on $\\mathbb{R}^d$, which is both common in practice and amenable to efficient gradient-based optimisation.\n\n**Our empirical results demonstrate the method’s relevance to both regression and classification tasks**. To see this, note that the kernel conditional mean embedding (KCME) can be directly used as a regression or classification model. In particular we point the reviewers attention to Figure 4. When the test function $h(y)$ is chosen such that $h(y) = y$, the KCME estimates $\\mathbb{E}[Y|X]$, which **is the object of interest in regression**. Moreover, for multi-class classification, in Figure 8 we report performance for test functions $h(y) = 1_{y=i}$, $i = 1, 2, 3, 4$. In this case we have that \n$$\n        \\mathbb{E}[1_{Y = i} | X] = \\mathbb{P}(Y = i | X),\n$$\nand hence Figure 8 reports the error in estimating the class conditional probability, which is the **object of interest in classification**. **Therefore wherever one may wish to do regression or classification, but do not have the availbe compute to handle a large amount of data, one may apply our methods.**\n\nBeyond these tasks, KCMEs have well-established applications (as discussed in the introduction), such as estimating conditional treatment effects in medical data [R5]. All of these applications fundamentally depend on the KCME’s ability to approximate conditional expectations of functions of random variables. Our empirical results show that this property is preserved under compression, with RMSE serving as a natural error metric, suggesting strong downstream performance in diverse domains.\n\n**We will stress this motivation mroe in the final version.**\n\n### **Question 2** - Could you clarify in the main text how ACKIP's complexity improves over ACKH --- specifically, why the inducing-point variant is $m$ times faster?\n\nGiven a dataset of size $n$, we aim to compress this down to $m$ data pairs. The cost of computing a single gradient in ACKIP is $\\mathcal{O}(m^3 + m^2n)$, hence if we take $J$ total gradient steps the overall cost is simply $\\mathcal{O}((m^3 + m^2n)J)$. \n\nConversely, ACKH grows the compressed set pair by pair. That is, at the $i$th iteration, the compressed set is of size $i$, and we are solving an optimisation problem by gradient descent where each gradient computation costs $\\mathcal{O}(i^3 + i^2n)$. Say we take $T$ steps to solve this optimisation problem, this then gives us a total cost for the i$th$ iteration of $\\mathcal{O}((i^3 + i^2n)T)$. However, we want to output a compressed set of size $m$, hence the total cost is actually \n\\begin{align*}\n        \\sum_{i=1}^m(i^3 + i^2n)T = \\mathcal{O}((m^4 + m^3n)T).\n\\end{align*}\nSee Section D.2.3 for the full derivation.\n\nIn words, the additional cost comes from the fact that at each iteration of the algorithm, even though we are only interested in optimising the single new pair, keeping all previously optimised pairs the same, we still have to do an $\\mathcal{O}(i^3)$ inverse, as it is not straightforward to separate the contribution of just the new pair to the loss function. Through the method of bordering, it is technically possible to update the inverse of a growing matrix, minimising re-computation. Unfortunately, bordering is a highly numerically unstable procedure, and experimental tests revealed this to be a very unstable approach. \n\nDue to reviewer guidelines, we cannot include figures in this discussion, however the below table shows the wall clock time for constructing a compressed set of size $m = 250$  targeting $n = 8000$ datapoints. **We will include a figure showing size of compressed set versus wall clock time in the final version of the paper.** We report the 25th, 50th and 75th percentiles over 20 runs, the results shows that **ACKIP is much faster than ACKH in practice**.\n\n|Method|Wall Clock Time (s)\n|-|-|\n|||\n|ACKH|294.4, 300.2, 345.8|\n|**ACKIP**| **11.40, 11.42, 11.45**|\n\n### **Question 3** - In Eq. (6), you introduced random-variable notations: X*, Y|X, Y'|X'. I understand this is for generality, but could you explain what these distributions represent? For example, is X* the empirical marginal of P(X,Y)?\n\nThank you for raising this. In this equation we introduced an additional distribution P(X*) on the feature space. This distribution is not necessarily related in any way to the existing joint distributions P(X, Y), P(X', Y'). The only connection between these distributions is that P(X*), P(X), and P(X') must share a measurable space, and for the purposes of the triangle inequality, in Theorem 4.1. we require that the relevant Radon-Nikodym derivatives are bounded. \n\n**To get a sense of what these distributions could be, it may be helpful to check the illustrative example in Section C.2 and in particular, Figure 28.**\n\n## **References**\n\n[R1] - Yutian Chen et al. “Super-Samples from Kernel Herding”. 2012\n\n[R2] - Raaz Dwivedi and Lester Mackey. \"Kernel Thinning\". 2024\n\n[R3] - Simon Mak and V. Roshan Joseph. \"Support points\". 2018\n\n[R4] - Dino Sejdinovic et al. “Equivalence of distance-based and RKHS-based statistics in hypothesis testing”. In: The Annals of Statistics 41.5. 2013\n\n[R5] - Junhyung Park, Uri Shalit, Bernhard Schölkopf, Krikamol Muandet. Conditional Distributional Treatment Effect with Kernel Conditional Mean Embeddings and U-Statistic Regression.\n\n[R6] - Rafael Izbicki and Ann B. Lee. “Nonparametric Conditional Density Estimation in a High-Dimensional Regression Setting”. 206.\n\n[R7] - Michael Arbel, Anna Korba, Adil Salim, Arthur Gretton. Maximum Mean Discrepancy Gradient Flow. 2019"}]

Author rebuttal:

Meta-review: The authors introduce kernel-based algorithms to produce compressed sets that approximate the joint or conditional distribution of a target dataset (extending the existing work on unlabeled datasets). Most of the concerns of the reviewers were addressed during the rebuttal (e.g., lack of non-kernel baselines, missing experiments) and now there is a consensus about accepting this paper. 

I recommend acceptance, but given than the topic is niche this would be a weak accept.
Decision: Accept (poster)