Efficient Conditionally Invariant Representation Learning
Authors: Roman Pogodin
Namrata Deka
Yazhe Li
Danica J. Sutherland
Victor Veitch
Arthur Gretton
Venue: ICLR 2023 notable top 5% (2023)
Keywords: conditional independence
kernel methods

Abstract: We introduce the Conditional Independence Regression CovariancE (CIRCE), a measure of conditional independence for multivariate continuous-valued variables. CIRCE applies as a regularizer in settings where we wish to learn neural features $\varphi(X)$ of data $X$ to estimate a target $Y$, while being conditionally independent of a distractor $Z$ given $Y$. Both $Z$ and $Y$ are assumed to be continuous-valued but relatively low dimensional, whereas $X$ and its features may be complex and high dimensional. Relevant settings include domain-invariant learning, fairness, and causal learning. The procedure requires just a single ridge regression from $Y$ to kernelized features of $Z$, which can be done in advance. It is then only necessary to enforce independence of $\varphi(X)$ from residuals of this regression, which is possible with attractive estimation properties and consistency guarantees. By contrast, earlier measures of conditional feature dependence require multiple regressions for each step of feature learning, resulting in more severe bias and variance, and greater computational cost. When sufficiently rich features are used, we establish that CIRCE is zero if and only if $\varphi(X) \perp \!\!\! \perp Z \mid Y$. In experiments, we show superior performance to previous methods on challenging benchmarks, including learning conditionally invariant image features. Code for image data experiments is available at github.com/namratadeka/circe.

Published as a conference paper at ICLR 2023
EFFICIENT CONDITIONALLY INVARIANT REPRESEN- TATION LEARNING
Roman Pogodin"
Namrata Deka*
Yazhe Li DeepMind & Gatsby Unit, UCL yazhe@google
Gatsby Unit, UCL
UBC
rmn- rmn-pogedi n i 1 com
dnamrata êcs ca
Danica J. Sutherland
Victor Veitch
Arthur Gretton Gatsby Unit. UCL arthur, www.ttgttggmmil.ccc.mm
UBC & Amii dsuthêcs ubc.ca
UChicago & Google Brain victorveitch&&oooe wwwp:/eei...cooooe......
ABSTRACT
We introduce the Conditional Independence Regression CovariancE (CIRCE), a measure of conditional independence for multivariate continuous-valued vari- ables. CIRCE applies as regularizer in settings where we wish to learn neural features (xX) of data X to estimate a target Y, while being conditionally indepen- dent of distractor Z given Y. Both Z and Y are assumed be continuous-valued but relatively low dimensional, whereas X and its features may be complex and high dimensional. Relevant settings include domain-invarian learning, fairness, and causal learning. The procedure requires just a single ridge regression from kernelized features of Z, which can be done in advance. is then only nec- essary to enforce independence of (xX) from residuals of this regression, which is possible with attractive estimation properties and consistency guarantees. By contrast, earlier measures of conditional feature dependence require multiple re- gressions for each step feature learning, resulting in more severe bias and vari- ance, and greater computational cost. When sufficiently rich features are used, we establish that CIRCE is zero if and only if (xX) IL | Y. In experiments, show superior performance previous methods challenging benchmarks, including learning conditionally invariant image features.
INTRODUCTION
We consider a learning setting where have labels Y that would like to predict from features X, and we additionally observe some metadata Z that we would like our prediction to be 'invariant' to. In particular, our aim learn a representation function o for the features such that (xX) T Z Y. There are at least three motivating settings where this task arises.
1. Fairness. In this context, Z is some protected attribute (e.g., race sex) and the condition xxX) 11 Z Y is the equalized odds condition (Mchrabi et al. 2021).
2. Domain invariant learning. In this case. Z a label for the environment in which the data was collected (e.g., if we collect data from multiple hospitals, Z: labels the hospital that the ith datapoint is from). The condition (XX 11. Z
sometimes used as a target for
invariant learning (c.g., Long et al. 2018 Tachet des Combes et al.) 22200 Goel al. 2021
Jiang & Veitch, 2022). Wang & Veitch (002)) argue that this condition is well mellvmotivtted cases where
causes X.
3. Causal represseattn learning. Neural networks may learn undesirable "shortcuts" for their tasks c.g., classifying images based on the texture of the background. To mitigate this issue, various schemes have been proposed to force the network to use causally relevant factors in its decision (e.g., Veitch al. 2021 Makar et al. 2022 Puli al. 2022). The structural causal assumptions used in such approaches imply conditional independence re- lationships between the features we would like the network to use, and observed metadata
"Equal contribution. Code for image data experiments is available at gigghuh.coomhamraaakkaacccnn

---

Published as a conference paper at ICLR 2023
that may wish to be invariant to. These approaches then try to learn causally structured representations by enforcing this conditional independence in a learned representation.
In this paper, we will be largely agnostic to the motivating application, instead concerning ourselves with how to learn a representation yp that satisfies the target condition. Our interest is in the (com- mon) case where X is some high nigh-dimensional structured data c.g., text, images, or video - and would like to model the relationship between X and (the relatively low-dimensional) Y, Z us- ing a neural network representation (X)). There are a number of existing techniques for learning conditionally invariant representations using neural networks (e.g., in all the motivating applications mentioned above). Usually, however, they rely on the labels Y being categorical with a small num- ber of categories. We develop a method for conditionally invariant representation learning that is effective even when the labels Y and attributes Z are continuous or moderately high-dimensional.
To understand the challenge, it is helpful to contrast with the task of learning a representation yp satisfying the marginal independence (x() TT Z. To accomplish this, we might define neural network to predict Y in the usual manner, interpret the penultimate layer as the representation ip, and then add a regularization term that penalizes some measure of dependence between (xX) and Z. As y changes at each step. we'd typically compute an estimate based on the samples in each mini-batch (e.g., |eutel et al. [019 Veitch et al. (202]). The challenge for extending this proce- dure to conditional invariance is simply that it's considerably harder to measure. More precisely, as conditioning on Y "splits" the available data we require large samples to assess conditional inde- pendence. When regularizing neural network training, however, we only have the samples available in each mini-batch often not enough for a reliable estimate.
The main contribution of this paper is a technique that reduces the problem of learning a condition- ally independent representation to the problem of learning a marginally independent representation, following a characterization of conditional independence due to Daudin (1980). We first construct particular statistic ((Y, Z) such that enforcing the marginal independence (xX) 1L <(Y, Z) is (approximately) equivalent to enforcing (X) I1 2 Y. The construction is straightforward: given fixed feature map (Y, Z) on y x 2 (which may be a kernel random Fourier feature map), we define Ç(Y, Z) as the conditionally centered features. Ç(Y, Z) = (Y, 2) W[ Z) Y]. We ob- tain a measure of conditional independence, the Conditional Independence Regression CovariancE (CIRCE), as the Schmmdt Norm of the kernel covariance between (x)) and Ç(Y, Z). A key point is that the conditional feature mean Elg((Y, Z) Y] can be estimated offline, in advance of any neural network training, using standard methods (Song et al., 2009; Grunewalder et al.) 2012 Park & Muandet 2020; Li et al., 2022). This makes CIRCE a suitable regularizer for any setting where the conditional independence relation (xX) 1L Z Y should be enforced when learning (X)). In particular, the learned relationship between Z and Y doesn't depend on the mini- nini-batch size. sidestepping the tension between small mini-batches and the need for large samples to estimate conditional dependence. Moreover, when sufficiently expressive features (those corresponding to characteristic kernel) are employed, then CIRCE is zero if and only if (XX) 11 Z Y: this result may be of broader interest, for instance in causal structure learning Zhang et al. (011) and
hypothesis testing [Pukumizu al. (2008); Shah & Peters (2020); /Huang et al. (2022).
Our paper proceeds as follows: in Section we introduce the relevant characterization of con- ditional independence from (Daudin 1980). followed by our CIRCE criterion we establish that CIRCE is indeed measure of conditional independence, and provide a consistent empirical esti- mate with finite sample guarantees. Next, in Section we review alternative measures of conditional dependence. Finally, in Section we demonstrate CTRCE in two practical settings: series of coun- terfactual invariance benchmarks due to Quinzan et al.] (2022), and image data extraction tasks on which a "cheat" variable is observed during training.
2 EFFICIENT CONDITIONAL INDEPENDENCE REGULARIZER
We begin by providing general- pprepose characterization of conditional independence. We then introduce CIRCE, a conditional independence criterion based on this characterization, which is zero if and only if conditional independence holds (under certain required conditions). We provide finite sample estimate with convergence guarantees, and strategies for efficient estimation from data.
If Y is categorical, naively we would measure marginal independence for each level of Y.
2

---

Published as a conference paper at ICLR 2023
2.1 CONDITIONAL INDEPENDENCE
We begin with a natural definition of conditional independence for real random variables:
Definition 2.1 (Daudin 1980 X and Z are Y-conditionally independent, X TL Z Y, if for all test functions g E Xx and E y2.. i.e. for all square-integrable functions of (X, Y) and (Z,Y) respectively, we have almost surely in Y that
Exz (9(X, Y) 2Z Y) |Y] = Ex (o(X, ()X, Ez (MZ
(1)
The following classic result provides an equivalent formulation:
Proposition 2.2 (Daudin 1980). X and 7. are Y-conditionally independent if and only if it holds for all test functions g E Ej = {g E Lax Ex [) = =0} and E E2 = {h E 12
Ez [b(2 = 0} that
(X Y) (2 = O.
Daudin 1980) notes that this condition can be further simplified (see Corollary A.3 for a proof):
Proposition 2.3 (Equation 3.9 of Daudin 1980). X and Z are Y Y-conditionally independent if and only if it holds for all g E L2 and h E E2 Th E 122 Ez (M( = =0} that
(lg(X))((,3)) = O.
(3)
An equivalent way of writing this last condition (see Lemma B. for formal proof) is:
for all g L and h e L2y, E [((X) (h( Ez (M(Z',)))i)) 0.
(4)
The reduction to g not depending on Y is crucial for our method: when we are learning the represen-
tation (xX). then evaluating the conditional expectations Ex (g() Y) YY] from Proposition 2.2
on every minibatch in gradient descent requires impractically many samples, but Ex [h Y) [Y]
does not depend on X and so can be pre-computed before training the network.
2.2 CONDITIONAL INDEPENDENCE REGRESSION COVARIANCE (CIRCE)
The characterization pairs of square-integrable functions g and We will now transform this condition into an easy-to- estimate measure that characterizes conditional independence, using kernel methods.
4 of conditional independence is still impractical, as it requires checking all
A kernel k(x,, x²) is a symmetric positive-definite function X'X + R. A kernel can be repre- sented as inner product k(I, x²) (Ø(z), 6(x')) for feature vector o(x) E H. where H. is a reproducing kernel Hilbert space (RKHS). These are spaces H. of functions f + R, with the key reproducing property (d(x), f'x f(z) for any f H. For M points
denote Kx row vector of o(x;), such that K X. is an M x matrix with k((;, x) entries and Xxx is an M x M matrix with k(r,, .ry) entries. For two separable Hilbert spaces G,F, a Hillbet-Schhidt operator A: A + F is a linear operator with a finite Hilbert-Schmidt norm
|| || = 1Ag,l3.
where (gibee beu is an orthonormal basis of G (for finite-dimensional Fuclidean spaces, obtained from linear kernel, A is just matrix and || its Frobenius norm). The Hilbert space HS(G, includes in particular the rank-one operators vó @ o for vp E F, G, representing outer products,
( & olg = &p (6. g)g. (A, vb & ))S(GG.F = (v. A
(6)
See Gretton 2022
Lecture 5) for further details.
We next introduce kernelized operator which (for RKHS functions g and h) reproduces the condi- tion in (4). which we call the Conditional Independence Regression CovariancE (CIRCE).
Definition 2.4 (CIRCE operator). Let 9 be an RKHS with feature map & X' G, and F an RKHS with feature map v
(Z x y) + F, with both kernels bounded: sup,]lø(r)] < oc, sups.y y)ll < oc. Let X, Y. and Z be random variables taking values in X.Y, and Z respec- tively. The CIRCE operator is
C Cx = E [x(() & (v(Z,Y) Ez [# Y) Y)) E HS(
3

---

Published as a conference paper at ICLR 2023
For any two functions g E 9 and h F, Definition 2.4 gives rise to the same expression in (4)
(CIZIY, &0
E (M(2) Ez (MZ
HS
The assumption that the kernels are bounded in Definition 2.4 guarantees Bochner integrability (Steinwart & Christmann| 2008 Def. A.5.20), which allows us to exchange expectations with inner products as above: the argument identical that of Gretton (2022 Lecture 5) for the case of the unconditional feature covariance. For unbounded kernels, Bochner integrability can still hold under appropriate conditions on distributions over which we take expectations, e.g. a linear kernel works if the mean exists, and energy distance kernels may have well-defined feature (conditional) covariances when relevant moments cxist (Sejdinovic et al. 2013).
Our goal now is to define kernel statistic which is zero iff the CIRCE operator 22 is zero. One option would be seek the functions, subject bound such as llllls S 1 and f S 1, that maximize (8); this would correspond to computing the largest singular value of Cxz For unconditional covariances, the equivalent statistic corresponds to the Constrained Covariance, whose computation requires solving an eigenvalue problem (e.g. Gretton et al.) 2005a Lemma 3). We instead follow the same procedure as for unconditional kernel dependence measures, and replace the spectral norm with the Tillbert-Schmid norm (Gretton et al. 2005b): both are zero when Ox Y is zero, but as we will see in Section 2.3 below, the Hilbert-Schmidt norm has a simple closed-form empirical expression, requiring no optimization.
Next, we show that for rich enough RKHSes G.F (including, for instance, those with a Gaussian kernel), the
norm of C2 characterizes conditional independence.
Theorem 2.5. For and F with L'-universal kernels (see, e.g., Sriperumbudur et al. 2011)
11Cx2|1 0 ina only if X 11 2
The "if" direction is immediate from the definition of C2 The "only if" direction uses the fact that the RKHS is dense L and therefore (8) is zero for all RKHS elements, it must be zero for all L functions. See Appendix B for the proof. Therefore, minimizing an empirical estimate of |10% X21Y [lss will approximately enforce the conditional independence we need.
Definition 2.6. For convenience, we define CIRCE(X, Z,Y) = =10
In the next two sections, construct differentiable estimator of this quantity from samples.
2.3 EMPIRICAL CIRCE ESTIMATE AND ITS USE AS A CONDITIONAL INDEPENDENCE REGULARIZER
To estimate CIRCE, we first need to estimate the conditional expectation ( =
Ez (Z, v) Y = yy. We defing x Y) = (Z) @ ((Y), which for radial basis kernels (e.g.
Gaussian, Laplace) is Lz-universal for (2 Therefore, Pzy|y (y) Ez [v(Z) = y] X
(1) = /z) (v) ply). The CIRCE operator be written
C X = [x(() @ (YY) @ (v(Z) (00())(22((()) (Y))
(10)
We need two datasets to compute the estimator: a holdout set of size M used estimate conditional expectations, and the main set of size B (e.g., a mini bani-b The holdout dataset is used to esti- mate conditional expectation lzzjjy with kernel ridge regression. This requires choosing the ridge parameter À and the kernel parameters for Y. We obtain both of these using leave-one-out cross- validation; we derive a closed form expression for the error by generalizing the result of Bachmann et al. (2022) to RKHS-valued "labels" for regression (see Theorem C.Ip.
We abuse notation in using 1 denote feature maps of (Y,Z), Y, and Z; in other words, we use the argument of the feature map to specify the feature space, to simplify notation.
Fukumizu et al. (2008) Section 2.2) show this kernel is characteristic, and Sriperumbudur et al. 2011 Figure (3)) that being characteristic implics L2 universality in this case.
4

---

Published as a conference paper at ICLR 2023
The following theorem defines empirical estimator of the Hilbert- -ehbert-Schhiit norm of the empirical CIRCE operator, and establishes the consistency of this statistic as the number of training samples B, M increases. The proof and formal description of the conditions may be found in Appendix C.2
Theorem 2.7. The following estimator of CIRCE for B points and M holdout points (for the con- ditional expectation):
CIRCE- B(B -) Tr (xxx (Kyr o @R22))
(11)
converges as Op(L/VB + 1/M(8-1)/1(840))) when the regression in Equation 30 is well- specified. Kxx and Kyy are kernel matrices of X and Y; elements of K?z are defined as k - (v(z) (2)y v²zz)= - -zz (w))); 3 E (1,2) characterizes how well-specified the solution is and p E (0, 1] describes the eigenvalue decay rate of the covariance operator over Y.
The notation Op(A) roughly states that with any constant probability, the estimator is O(A).
Remark. For the smoothly well-specified case we have 3 2, and for a Gaussian kernel p is arbi- trarily close to zero, giving a rate Op(1/v + 1/M The 1/M rate comes from conditional expectation estimation, where it is Munimax-optimee for the well-specified case (Li et al. 2022)
Using kernels whose eigenvalues decay slower than the Gaussian's 's would slow the convergence rate Theorem 2).
(see Li et al. 2022
The algorithm summarized in Algorithm We can further improve the computational complexity for large training sets with random Fourier features (Rahimi & Recht 2007); see Appendix [D]
Algorithm Estimation of CIRCE
Holdout data ((z,, = mini-batch {(r4, 24, )))
Holdout data
Leave-one-out (Theorem C.1 for (ridge parameter) and σy (parameters of Y kernel);
((x))) (Krr Kx 1
X, o, arg min Σ
(1- (Kr
W = (K + 11 W2 WiKzzW,
Mini-batch
Compute kernel matrices Keui Kyys Ky,, Kyz (I, U..U.- mini-batch, Y, Z: holdout)
k Kyy ② K== Kyr WiyWKK ( W1 Kzz) + KKr
CIRCE B Tr (Kakee)
We can of empirical CIRCE regularizer for conditionally independent regularization learning, where the goal is to learn representations that are conditionally independent of a known distractor Z. We switch from X to encoder yo (X). If the task is predict Y using some loss (X), Y), the CIRCE regularized loss with the regularization weight y >> 0 is as follows:
min (X)) + CTCCE(()()))) "
(12)
RELATED WORK
We review prior work kernel-based measures of conditional independence determine force 11 Z Y, including those measures we compare against in our experiments in Section 4 We begin with procedures based on kernel conditional feature covariances. The conditional ker- nel cross-covariance was first introduced as a measure of conditional dependence by (Sun et al. (2007). Following this work, kernel-based conditional independence test (KCI) was proposed by Zhang et al. 22011). The latter test relies on satisfying Proposition 2.2 leading to statistiq") that requires regression of (xX) on in every minibatch (as well as of Z on Y. in our setting). More
'The conditional indeeenddncee test statistic used by KCI is 1/ Tr (K ( where X (x, Y) and K' centered kernel matrix. Unlike CIRCE, K Kxi requires regressing X using kernel ridge regression.
5

---

Published as a conference paper at ICLR 2023
recently, Quinzan et al. (0022) introduced variant of the Hilbert-Schmidt Conditional Indepen- dence Criterion (HSCIC: Park & Muandet (2020) as a regularizer to learn a generalized notion of counterfactually--nvaiiia representations (Veithh et al., 2021b. Estimating HSCIC(X, Z from finite samples requires estimating the conditional meen-enb jx. M and JzzlY via regressions (Grunewalder al.] 2012). HSCIC requires three times many regressions as CIRCE, of which two must be done online in minibatches to account for the conditional cross-covariance terms involving X. We will compare against HSCIC in experiements, being representative of this class of methods, and having been employed successfully in setting similar to ours.
Alternative measures of conditional independence make use of additional normalization over the measures described above. The Hilbert-Scee Hilbert-Schhidt norm of the normalized cross- cross-covariance was in- troduced as test statistic for conditional independence by Fukuumiu et al. (2008), and was used for structure identification in directed graphical models. Huang et al. (2022) proposed using the ratio of the maximum mean discrepancy (MMD) between PxIzY and PxIY. , and the MMD between the Dirac measure at X and Pxxy,, measure of the conditional dependence between X and Z given Y. The additional normalization terms in these statistics can result in favourable asymptotic proper- ties when used in statistical testing. This comes the cost of increased computational complexity, and reduced numerical stability when used as regularizers on minibatches.
Another approach, due to Shah & Peters (2020), is the Generalized Covariance Measure (GCM). This is a normalized version of the covariance between residuals from kernel-ridge regressions of X on Y and Z Y (in the multivariate case, maximum over covariances between univariate regressions is taken). As with the approaches discussed above, the GCM also involves multiple regressions one of which (regressing X on Y) cannot be done offline. Since the regressions are univariate, and since GCM simply regresses Z and X on Y (instead of (=22, Y)) and é(X) ()) on Y). we anticipate that GCM might provide better regularization than HSCIC on minibatches. This comes at cost, however, since by using regression residuals rather than conditionally centered features, there will be instances of conditional dependence that will not be detectable. We will investigate this further in our experiments.
EXPERIMENTS
We conduct experiments addressing two settings: (1) synthetic data of moderate dimension, study effectiveness of CIRCE at enforcing conditional independence under established settings (as envis- aged for instance in econometrics or epidemiology); and (2) high dimensional image data, with the goal of learning image representations that are robust to domain shifts. We compare performance over all experiments with HSCIC (Quinzan et al. 2022 and GCM (Shah & Peters 2020).
4.1 SYNTHETIC DATA
We first evaluate performance on the synthetic datasets proposed by Quinzan et al. (2022): these use the structural causal model (SCM) shown in Figure I and comprise 2 univariate and 2 multivariate cases (see Appendix for details). Given samples of A, Y and Z. the goal is to learn predictor B = ((A, Y, Z) that is counterfac- tually invariate to Z. Achieving this requires enforcing conditional independence Y, 2) IL Y For all experiments on synthetic data, we used fully connected network with 9 hidden layers. The inputs of the network were A. Y and Z. The task is to predict B and the network is learned with the MSE loss. For each test case, we generated 10k examples, where 8k were used for training and 2k for evaluation. Data were normalized with zero mean and unit standard deviation. The rest experimental details provided in Appendix E
A
B
Figure 1: Causal structure for synthetic datasets.
We report in-domain MSE loss, and measure the level of counterfactual invariance of the predictor using the VCF (Quinzan et al. 20222 eq. 4; lower is better). Given X = Y,,Y
VCF = E V
E
[ =
(13)
PB ix is the counterfactual distribution of B given X = x and an intervention of setting = to 2'.

---

Published as a conference paper at ICLR 2023
Univariate Cases Table | summarizes the in-domain MSE loss and VCF comparing CIRCE to baselines. Without regularization, MSE loss is low in-domain but the representation is not invariant to changes of Z. With regularization, all three methods successfully achieve counterfactual invari- ance in these simple settings, and exhibit similar in-domain performance.
No Reg
GCM
HSCIC
CIRCE
Case
MSE
VCF
MSE
VCF
MSE
VCF
MSE
VCF
1
2.03e-4
0,180
0.198
2.59e-06
0.197
2.08e-11
0.197
8.77e-08
2
0.027
0.258
1.169
9.07e-07
1.168
3.08e-11
1.168
7.37e-11
Table 1: MSE loss and VCF for univariate synthetic datasets. Comparison of representation without conditional independence regularization against regularization with GCM, HSCIC and CIRCE.
Multivariate Cases We present results on 2 multivariate cases: case 1 has high dimensional Z and case 2 has high dimensional Y. For each multivariate case, vary the number of dimensions = {2, 5, 10, 20). To visualize the trade-offs between in-domain performance and invariant rep- resentation, we plot the Pareto front of MSE loss and VCF. With high dimensional Z (Figure A CIRCE and HSCIC have a similar trade-off profile, however it is notable that GCM needs to sac- rifice more in-domain performance the GCM statistic is a maximum over normalized covariances of univariate residuals, which can be less effective in multivariate setting, For high dimensional Y (Figure 23), the regression from Y to ub( (Z.) is much harder. We observe that HSCIC becomes less efficient with increasing d until at 20 fails completely, while GCM still sacrifices more in-domain performance than CIRCE.
achieve the same level of invariance. This may be because
A 0.0
d=2
d=s
d=10
d=
0.0
0.8
0.0
CIRCE
GEM
0.4
5 0.4
0.4
0.4
0.2
0.2
0.2
0.2
0.0
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
MSE Loss
MSE Loss
MSE Loss
MSE Loss
B
d-5
0.0
d-10
CCM
PSCIC
$
0.0
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
MSE
MSE Lozs
MSE Loss
Loss
Figure 2: Pareto front of MSE and VCF for multivariate synthetic dataset. A: case 1; B: case 2.
4.2 IMAGE DATA
We next evaluate our method on two high-dimensional image datasets: d-Sprites (Matthey et al. (2017) which contains images of 2D shapes generated from six independent latent factors; and the Extended Yale-B Face dataset Georghiades et al. (2001)) of faces of 28 individuals under varying camera poses and illumination. We use both datasets with the causal graph in Figure 3 where the image X is directly caused by the target variable Y and distractor Z. There also exists strong non-causal association between Y and Z in the training set (denoted by the dashed edge).
Y
X
Figure 3: Causal structure for dSprites and Yale-B. Dashed line denotes non-causal as- sociation between nodes.
The basic setting is as follows: for the in-domain (train) samples, the observed Y and Z are correlated through the true Y as
Y ~ Py, & ~ N((0 oz), Y' = Y + Ey ~ o)),o,)
Z = 3
(14)
z' = fx,, x f=
(15)
Google and DeepMind do have access handle the Yale-B Face dataset.
7

---

Published as a conference paper at ICLR 2023
Y and Z are observed; fa is the structural equation for Z' (in the simplest case Z' = Z); fo is the generative process of X. Y and Z' represent noise added during generation and are unobserved.
A regular predictor would take advantage of the association & between Z and Y during training, since this is a less noisy source of information on Y. For unseen out-of-distribution (OOD) regime, where Y and Z are uncorrelated, such solution would be incorrect.
Therefore, our task is to learn a predictor (X) that is conditionally independent of Z: ((X) TL YIY, so that during the OOD/testing phase when the association between Y and Z ceases to exist, the model performance is not harmed as it would be if (x()) relied on the "shortcut" Z to predict Y. For all image experiments we use the AdamW (Loshchilov & Hutter (2019)) optimizer and anneal the learning rate with cosine scheduler (details in Appendix F). We select the parampparsessess of the optimizer and scheduler via grid search to minimize the in-domain validation set loss.
4.2.1 DSPRITES
Of the six independent generative factors in d-Sprites, we choose the y-coordinate of the object as our target Y and the z-coordinate of the object in the image as our distractor variable Z. Our neural network consists of three convolutional layers interleaved with max pooling and leaky ReLU activations, followed by three fully-connected layers with 128, 64, unit(s) respectively.
Linear dependence We sample images from the dataset per the linear relation Z'= Y c.-- We then translate all sampled images (both in-domain and OOD) vertically by Ey. resulting in an observed object coordinate of (2, Y + Ey). In this case, linear residual methods, such as GCM, are able to sufficiently handle the dependence as the residual Z - E Y = &= is correlated with Z which is the observed n-coordinate. As a result, penalizing the coss-covvr between sp (X) -E (xx) Y| and ZEE [Z] Y will also penalize the network's dependence on the observed rr-oordiinate to predict Y.
CIRCE
HSCIC
0.150
In-domain
0.150
dome In
0.150
dn-domain
0.125
..* trained DoG
ocp
0.125
...
Uraimed on 0D0
0.125
OOD trained DOC
MSE luse
0.100
0.100
loze
0,100
0.075
0.075
0.075
0.050
0.050
0.050
0.025
0,025
0.025
0.000
0.000
0.000
10a
10
10a
10a
20
20
10a
10-2
10-1
regu regularization strangth y
regularization strength
regularization strength y
Figure 4: dSprites (linear). Blue: in-domain test loss; orange: out-of-domain loss (OOD); red: loss for OOD-trained encoder. Solid lines: median over 10 seeds; shaded areas: min/max values.
In Figure plot the in-domain and OOD losses over range of regularization strengths and demonstrate that indeed GCM is able to perform quite well with a linear function relating to Y. CIRCE is comparable GCM with strong regularization and outperforms HSCIC. To get the optimal OOD baseline we train our network on an OOD training set where Y and Z are uncorrelated.
Non-linear dependence To demonstrate the limitation of GCM, which simply regresses Z on Y instead of v/ ((Z Y) on Y, we next address a more complex nonlinear dependence 3(Y 0 and Z' = Y + a Z The observed coordinate of the object in the image is (Y + a& Y E.)) - For small a, the unregularized network will again exploit the shortcut, i.e. the observed r-coordinate, in order to predict Y. The linear residual, if we don't 't use features of Z. Z E [Z YJ = &s. which is uncorrelated with Y + ag?, because E [E2]] = O due to the symmetric and mero distribution of E.. As result, penalizing cross-covariance with the linear residual (as done by GCM) will not penalize solutions that use the observed r-coordinate to predict Y. Whereas CIRCE which uses a feature map (2) can capture higher order features. Results are shown in 5 we see again that CIRCE performs best, followed by HSCIC, with GCM doing poorly. Curiously, GCM performance does still improve slightly on OOD data as regularization increases we conjecture that the encoder (p(X) may extract non-linear features of the coordinates. However, GCM is numerical unstable for large regularization weights, which might arise from combining a ratio normalization and a max operation in the statistic.
8

---

Published as a conference paper at ICLR 2023
CIRCE
HSCIC
GCM
0.150
0.150
0.250
0.125
11a
000
0.125
trained on 900
0.125
0.100
0.300
MSE loss
0.300
m-domain
MSE
0.075
0.075
0.075
tranned on OCO
300
0.050
0.050
0.025
0.025
0.625
0.000
0.000
0.000
10c
10t
10a
10
10
10a
10
10-4
10
regulatication strength
regularization strength
regularization strength
Figure 5: dSprites (non-linear). Blue: in-domain test loss; orange: out-of-domain loss (OOD); red: loss for OOD-trained encoder. Solid lines: median over 10 seeds; shaded areas: min/max values.
4.2.2 EXTENDED YALE-B
Finally, we evaluate CIRCE as a regressor for supervised tasks on the natural image dataset of Extended Yale-B Faces. The task here is to estimate the camera pose Y from image X while being conditionally independent of the illumination Z which is represented as the azimuth angle of the light source with respect the subject. Since, these are natural images, we use the ResNet- 18 (He) iet al.] 2016) model pre-trained on ImageNet (Deng et al. 2009) to extract image features, followed by three fully-connected layers containing 128, 64 and unit(s) respectively. Here we sample the training data according to the non-linear relation Z' = Z = 0.5(Y + =Y²), where E is either +1 = 0.5Y 0.5Y [ Y = 0.5Y, and thus the linear residuals depend on Y. (In experiments, Y and are re-scaled to be in the same range. We avoid it here for simplicity.) Note that GCM can in principle find the correct solution using a linear decoder. Results are shown in Figure 6 CIRCE shows small advantage over HSCIC in OOD performance for the best regularizer choice. GCM suffers from numerical instability in this example, which leads to poor performance.
or with equal probability. In this case [Z] YY]
CIRCE
HSCIC
0.150
Instomain
0.150
In-dammin
0.150
In-tomain
0.125
OGD
trained on COD
0.125
... trained on 0CD
000
0.125
trained 00D
OOD:
0.1.00
0.300
0.100
MSE
0.075
0.075
0.075
0.050
0.050
0.050
0.025
0.025
0.025
0.000
0.000
0.000
100
regularization strength V
reqularization strength
regu lariaiizatoon strength y
Figure 6: Yale-B. Blue: in-domain test loss; orange: out-of-domain loss (OOD); red: loss for OOD- trained encoder. Solid lines: median over 10 seeds; shaded areas: min/max values.
DISCUSSION
We have introduced CIRCE: a kernel-based measure of conditional independence, which can be used as a regularizer to enforce conditional independence between a network's 's predictions and a pre-specified variable with respect to which invariance is desired. 'he technique can be used in many applications, including fairness, domain invariant learning, and causal representation learning- Following an initial regression step (which can be done offline), CIRCE enforces conditional inde- pendence via a marginal independence requirement during representation learning, which makes well suited minibatch training. By contrast, alternative conditional independence regularizers quire an additional regression step on each minibatch, resulting in a higher variance criterion which can be less effective in complex learning tasks.
As future work, it will be of interest to determine whether or not CIRCE is statistically significant on given dataset, as employ it as statistic for test of conditional dependence.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work supported by DeepMind, the Gatsby Charitable Foundation, the Wellcome Trust, the Canada CIFAR AI Chairs program, the Natural Sciences and Engineering Resource Council of Canada, SHARCNET, Caleul Québec, the Digital Resource Alliance of Canada, and Open Philan- thropy. Finally, we thank Alexandre Drouin and Denis Therien for the Bellairs Causality workshop which sparked the project.
REFERENCES
Gregor Bachmann, Thomas Hofmann, and Aurélien Lucchi. Generalization through the lens of leave-one-out error. ICLR, 2022.
Alex Beutel, Jilin Chen, Tulsee Doshi, Hai Qian, Allison Woodruff, Christine Luu, Pierre Kreit- mann, Jonathan Bischof, and Ed H. Chi. Putting fairness principles into practice: Challenges, metrics, and improvements. In AIES, 2019.
Daudin. Partial association measures and an application to qualitative regression. Biometrika, 67 (3):581-590, 1980.
Jia Deng. Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In CVPR, pp. 248-255, 2009.
Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares algo- rithms. JMLR, 21:205-1, 2020.
K. Fukumizu, A. Gretton, Sun, and B. Schölkopf. Kernel measures of conditional dependence. In NeurlPS, 2008
A.S. Georghiades, P.N. Belhumeur, and D.J. Kriegman. From few many: Illumination cone models for face recognition under variable lighting and pose. IEEE T-PAMI, 23(6):643-660, 2001.
Karan Goel, Albert Gu, Yixuan Li, and Christopher Ré. Model patching: Closing the subgroup performance gap with data augmentation. In ICLR, 2021.
A. Gretton. Introduction to RKHS, and some simple keree algorithms. Lecture Notes, Gatsby Computational Neuroscience Unit, 2022. URL http::ttt/////tt gat ucl uk/ html
A. Gretton, R. Herbrich, J. Smola, O. Bousquet, and Schölkopf. Kernel methods for measuring independence. JMLR, 6:2075-2129, 2005a.
Arthur Gretton, Olivier Bousquet, Alex Smola, and Bernhard Schölkopf. Measuring statistical de- pendence with Hilbert-Schmidh norms. In ALT, pp. 63-77, 2005b.
Grunewalder, G. Lever, L. Baldassarre, Patterson, A. Gretton, and M. Pontil. Conditional mean embeddings as regressors. In ICML, 2012.
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. CVPR, pp. 770-778, 2016.
Zhen Huang, Nabarun Deb, and Bodhisativa Sen. Kernel partial correlation coefficient measure of conditional dependence. JMLR, 23(216):1-58, 2022.
Yibo Jiang and Victor Veitch. Invariant and transportable representations for anti-causal domain shifts, 2022.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
I. Klebanov, Schuster, and T.J. Sullivan. A rigorous theory of conditional mean embeddings. SIAM Journal on Mathematics of Data Science, 2(3):583-606, 2020.
10

---

Published as a conference paper at ICLR 2023
Zhu Li, Dimitri Meunier, Mattes Mollenhauer, and Arthur Gretton. Optimal rates for regularized conditional mean embedding learning. arXiv preprint arXiv:2208.01711 2022.
Mingsheng Long, Zhangjie Cao, Jianmin Wang. and Michael Jordan. Conditional adversarial
domain adaptation. In NeurIPS, volume 31, 2018.
Iyya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In ICIR, 2019.
Maggie Makar, Ben Packer, Dan Moldovan, Davis Blalock, Yoni Halpern, and Alexander D' Amour. Causally motivated shortcut removal using auxiliary labels. In AISTATS, 2022.
Loic Matthey, Irina Higgins, Demis Hassabis, and Alexander Lerchner. dsprites: Dis-
entanglement testing sprites dataset, 2017. URL htttps://gitau. com/ deepmind/ disprites-dataset
Colin McDiarmid. On the method of bounded differences. Surveys in combinatorics, 141(1):148- 188, 1989.
Ninarch Mchrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Comput. Surv, 54(6), 2021.
M. Mollenhauer and P. Koltai. Nonparametric approximation of conditional expectation operators. arXiv preprint arXiv:2012.129111 2020.
Junhyung Park and Krikamol Muandet. measure-theoretic approach to kernel conditional mean
embeddings. In NeurIPS, 2020.
Aahlad Manas Puli, Lily H Zhang, Eric Karl Oermann, and Rajesh Ranganath. Out-of-distribution generalization in the presence of nuisance-induced spurious correlations. In ICLR, 2022.
Francesco Quinzan, Cecilia Casolo, Krikamol Muandet, Niki Kilbertus, and Yucen Luo. Learning counterfactually invariant predictors. arXiv preprint 220.:22007.09668. 2022.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In NeurlPS, 2007.
D. Sejdinovic, B. Sriperumbudur, A. Gretton, and K. Fukumizu. Equivalence of distance-based and rkhs-based statistics hypothesis testing, Annals of Statistics, 41(5):2263-2702, 2013.
Rajen D Shah and Jonas Peters. The hardness of conditional independence testing and the gener- alised covariance measure. The Annals of Statistics, 48(3):1514-1533 2020.
L. Song, J. Huang, A. J. Smola, and K. Fukumizu. Hilbert space embeddings of conditional distri- butions. In ICML., 2009.
B. Sriperumbudur, K. Fukumizu, and G. Lanckriet. Universality, characteristic kernels and RKHS embedding of measures. JMLR, 12:2389-2410, 2011.
Ingo Steinwart and Andreas Christmann. Support Vector Machines. Information Science and Statis- tics. Springer, 2008
X. Sun, D. Janzing. B. Schölkopf, and K. Fukumizu. A kernel-based causal learning algorithm. In ICML. pp. 355-862, 2007.
Remi Tachet des Combes, Han Zhao, Yu-Xiang Wang. and Geoffrey Gordon. Domain adaptation with conditional distribution matching and generalized label shift. NeurIPS, 2020.
Victor Veitch, Alexander D' Amour, Steve Yadlowsky, and Jacob Eisenstein. Counterfactual invari- ance to spurious correlations text classification. NewrIPS, 2021.
Zihao Wang and Victor Veitch. unified causal view of domain invariant representation learning. In ICML Workshop Spurious Correlations, Invariance and Stability, 2022.
Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. In UAI, 2011.
11

---

Published as a conference paper at ICLR 2023
APPENDICES
A CONDITIONAL INDEPENDENCE DEFINITIONS
We first repeat the proof of the main theorem in Daudin 1980 as the missing proofs we need for the altermative definitions of independence rely on the main one.
Theorem A.1 (Theorem 1 of Daudin 1980). Define Ei = :g:9 E 1y, E [g] = 0}. E2 = {h: Ly E [h] Y] = 0}. Then, the following two conditions are equivalent: E 91 h1] = 0
Vgi E E1. th E Eg.
E La YJ E B
Vg E Lxv, vh Lyz
Proof. Necessary condition: EE Igh Y| B Y]
E[ghh1] = 0
Because E1 S Lxxy and E2 C Lyz for 91 E Ei and h1 E Es we have
E h
Y|=
Y] = E 19 Y [4 Y|=0
h1 By Y] 0.
Sufficient condition: E[ghh1] =
E igh - Y
Let g' - E [g Y| where g E L and h = h |A Y where h E L Then, g' E E₁ and h' E Eg
Blg'h h'1
E [gg [g Y [) (4- [b])]
= E [gh - hE Y - 9 Y + E 1g
YY
Ey E [[gh hE gE h Y E Y i [YD
= Ey E [gh Y -
E [
= O.
(16)
Let B be Borel set of the image space of Y, g* -gTB where In is indicator function of B. We have [ 2d T = Jg dPP - f < co, therefore g" E 12x--
Using
Equation (16).
Ey E [g" Y [h Y]
By [ B -1 [g|B Y [ Y]]
E [gh Y] Y] E
Y E (1 Y dP
So E [gh] Y] = E [g Y E [/] Y] almost surely.
Corollary A.2 (Equation 3.8 of Daudin 1980). The following two conditions are equivalent:
E [ghh] =0 E [gh Y
Vgg E L'x,, wh, E Ez, Vg Lxv, wh LÝz
Eb
Proof. Necessary condition is identical to the previous proof.
Sufficient condition: E[ght] = - E [gh Y = lg [|
Let h h - --EEl [h [ where h E L2 then h' E Ez
Elgh'l EE(g( [h D
EEggh g TE. [h ]]
Ey [E [[gh
E [l Y Y]
Ey E [gh Y [h E Y Y
Ey [E [gh Y E
= 0.
Using the same argument for Theorem
A.1.
E. [gh Y
E
Y E (h YY] almost surely.
12

---

Published as a conference paper at ICLR 2023
Corollary A.3 (Equation 3.9 of Daudin 1980). The following two conditions equivalent:
[g hi] gg Y
Vg E &1,,vh, 4h1 E E Ag E L wh Lyz
1g |
Proof. Necessary condition: As E2 [ l and 1 s Lxx.
E [ h YJ E
Ih A =
Sufficient condition:
Elghhi] = - E [gh Y| = E Y ||]
Take a simple function ye E.=1,,,, a for integrable Borel set A, in XY. As integrable simple functions are dense in x, we only need to prove the condition for all ga-
In our case, the indicator function decomposes Ia. TAx I Ay, and therefore for gi a. AM
n
9a Σ ge gelax
Therefore,
12
Elgah1 E
A E 1 Y]
E
Σ
Ay
0.
immediately have E[ght] Applying Corollary A.2 concludes the proof.
As simple functions dense in T2
0 Vgg E 12 /y Eg-
B CIRCE DEFINITION
First, need more convenient function class:
Lemma B.1. The function class E2 = { L2n E Y 0} coincides with the function class
Fy (h' l
I [h Y) h E T.22y;
Proof. E2 C Fig: any h E Fz is in 1,3y and has the form h h- E [h Y| by construction because the last term is zero.
Ey Ez: first, any h E Eyy satisfies E [ YY] 0 by construction. Second,
f (1)) du(Z, = / (h E [h Y 2 du(Z,Y)
(17)
/ (12 (12-2h 2h 2h + +)+ du(z,t)
(18)
= / (12 18-((BMM (B(I))))² du(Z,Y) +00,
(19)
as h E Liyy and the second term is non-positive.
Proof of Theorem 2.5 For the "if" direction, we simply "pull out" the Y expectation in the defini- tion of the CIRCE operator and apply conditional independence:
X = Ey [x < (Ez (2,YY YJ Ez (4b
YJ) = 0.
For the other direction, first, | HS 0 implies that for any g E G and F.
[g (h - E [1 YJ) 0
(20)
13

---

Published as a conference paper at ICLR 2023
by Cauchy-Schward
Now, we use that an Ln-universal kernel is dense in L by definition (see Sriperumbudur et al. (0111). Therefore, for any L and h E Lzy, for any > 0 we find g. 9 and he F such that
lgg gell2 S c, ||l h. c. For the L function, we can now write the conditional independence condition as
(21)
E [g (h 1
[h
E [[g ge) (4 + he E [h he [J]
(22)
= 0 + E [[g 9-) (h he 1 1h - h. YDJ
(23)
+ E Ig (h he E [h h. [Y] E [gg ge) (h.
[he [Y)]
(24)
The first term is zero because ||Cx = 0. For the rest, we need to apply Cauchy-Schwarc
E [[gg 9.) (h- h.)l s l1g --lll /| hell S e² E [gg 9c) (EE [h he YYJ I lgg 9ell2 |1h hell2 S
(25)
(26)
where in the last inequality we used that E (E [X | IE [x]] for conditional expectations. Similarly, also using the reverse triangle inequality, E [g. (h- he)l S e || S (1]g]12 +)
(27)
Repeating this calculation for the rest of the terms, we can finally apply the triangle inequality to show that
E La (4 - E [M 2 + 2 (Il9l22 + +e) 2e (1]/ll2 + +e)
(28)
2e (3 119122 |[/ll2)
(29)
As Igllz and 1 are fixed and finite, we can make the bound arbitrary small, and hence [g (h- E Y
D] -.
C PROOFS FOR ESTIMATORS
C.I ESTIMATING THE CONDITIONAL MEAN EMBEDDING
We will construct an estimate of the term Ez job Z, YY] that appears inside CIRCE, as a func- tion of Y. We summarize the established results on conditional feature mean estimation: see (Grunewalder et al. 2012; Park & Muandet 2020; Mollenhauer & Koltai 2020; Klebanov et al.) 2020 Li et al. 2022) for further details. To learn I. (+()) Y] for some feature map v0(4) E Ho
and random variable Q (both to be specified shortly), we can minimize the following loss:
(v)):(()==
arg min FEBOY
Σ (1b(())) - F(u)) + +1IIFI2
(30)
where Goy is the space of functions from to Ho. The above solution said to be well-specified
when there exists Hilbert-Schmidt operator A E HS(Hy, Ho) such that F (v) = A" A²)(v) for
all y E V, where Hy is the RKHS on y with feature map (v() (Li et al. 2022
We now consider the case relevant to our setting, where Q (Z, Y). We define (Z.Y) *b (Z) & (YY), which for radial basis kernels (c.g. Gaussian, Laplace) Lz-universal for (Z, Y
We then write Ez (z,, y) Y y] Ez [x) |Y = y @ vv)). The conditional feature mean
(Z) Y] can be found with kernel ridge regression (Grunewalder et al. 2012 Li et al. 2022 :
( = E (z) Y (3) v Kyy (Kyy + AZ) K
(31)
'We abuse notation using 1 to denote feature maps (Y, 2), Y, and Z: other words, we use the argument of the feature map to specify the feature space, to simplify notation.
Fuuumizu et al. (2008, Section 2.2) show this kernel is characteristic, and Sriperumbudur et al. 2011 Figure (3)) that being characteristic implics La universality in this case.
14

---

Published as a conference paper at ICLR 2023
where Kg indicates "matrix" with rows (2z),, (Kyy), k.j kyy,, Vj), and (Kyy): ); = kyy V/). Note that we have used the argument of k to identify which feature space it pertains to i.c., the kernel on Z need not be the same that on Y.
We can find good choices for the Y kernel and the ridge parameter by minimizing the leave-one- out cross- validaaioo error. In kernel ridge regression, this is almost computationally free, based on the following version of classic result for scalar-valued ridge regression. The proof generalizes the proof of Theorem 3.2 of [Bachmann et al. (2022) RKHS-valued outputs.
Theorem C.1 (Leave-one-out for kernel mean embeddings). Denote the predictor trained the full dataset as Fs, and the one trained without the i-th point as F-i. For X > and
= KyY (Kyy + xT)= the leave-one-out (1.0)) error for Equation 330
Σ 1
N
- FFi())---((()l)
1
N (1:)
FFs
(32)
N
N
(1 (1- Aa)
Proof. Denote the full dataset S = (vVi =x) the dataset missing the i-th point is denoted S-i- Prediction on the full dataset takes the form F(Y) = AKz
Consider the prediction obtained without the M-th point (w.l.ogg)) but evaluated on yMr F- M (yM). Define a new dataset Z S_M (LUM,F-MM (yM))) and compute the loss for it:
M-1
L2(F-M) = Σ [1(())) - FFM H2 + [1F-M(UM - F-M(UN) + AIIF- MA-MMl 11.22r (33)
1=1
Ls
LS (F) S Ls (F) + [[FM((MM) F(UM))R S Lz()), (34)
where the first inequality is due to F- minimizing Ls- Therefore, F-M also minimizes Lz- As A in the prediction expression FYs(Y) AKz. depends only Y, and not on Z, P-M M has to
have the same form as the full prediction:
Ka.. = (b()))
i< M i i= M
F F = AKg
(35)
(FM((
This allows to solve for F F-M(UM).
F-M(UM) KyNs (Kyx +X1) Kg. Σ Ama((Z))
(36)
M-1 Amsab(2)) + AMMU(Z)) # AMMN((EM)
(37)
M
Ameb(2))) - AMAr((EM) + AmarD(())
(38)
==1
FS(UM) AMMN((EM) + AMMu((Z))
(39)
Fs(yM) AMMrV(ZMM) AMMMF-M(MMM)
(40)
As AMM is a scalar, we can solve for F-M
FuMr = FS(UM) AMMU(EE
(41)
AMM
Therefore,
(2MM) F-M(UM)) (1 AAsM))((EES) Fs(UM) AMMr((MM)
(42)
AMM
((ZM) - Fs(UM)
(43)
1 AMM
Taking the norm and summing this result over all points (not just M) gives the LO0 error.
15

---

Published as a conference paper at ICLR 2023
C.2 CIRCE ESTIMATORS
Lemma C.2. For B points and K = (V(z) - E [2] (0=)) - [2 (v")), the CIRCE
estimator
11 x 12 HS B
Tr (Kxx (Kyy @ K2z))
(44)
has O(1/B) bias and (1/1// deviation from the mean for any fixed probability of the deviation.
Proof. The bias is straightforward:
1
E (r (Xxx @ Kzz))l
B(B-1)
1
E
Σ 8.37/
Kerzy Kyiss 22
+
E
Σ
Ken Kyy. K
B(B 11)
B(B
1)
Eo ant (K K K hig
Σ
+0
B(B 1)
B
=1C%xoliis +0
B
For the variance, first note that our estimator has bounded differences. Denote Krr Kyy & K2 and t = (y, =). if we switch one datapoint (xi,4; 4;) to (xt (') and denote the vectors with switch coordinates as X
[Tr (KxxKrT) Tr (Kxix:(Terri)
Kerz Kun Kefz + Σ (Krj KejatKejt
< (2 4(B 1))K2 me max I (4B 2) max maxk? max
Therefore, for any index
1
IT (Kxx (Kyr K22)) Tr (Kxixi (Kyivi K2.z)))
B(B- -)
4B 2
Kn max Ky max K max
B(B 1)
We can now use McDiarmid's inequality McDiarmid 1989) with
4B-2 2 K₂ maxK maxk?
c= B(B - 1)
meaning that for any
Tr (KxxKTT)
Tr (KxXKIT)
2 Be²
P
-E
26)
2 exp
B(B- 1)
B(B - 1)
2c 2e² - 1)2
= exp
(AB - 2)2 max K3 max K2c max
Therefore, for any fixed probability the deviation from the mean decays as O(1/VB).
Definition C.3. A (3, p) kernel for given data distribution satisfies the following conditions (see
Fischer & Steinwart 2020); et al. (002) for precise definition using interpolation spaces):
(EVD) Eigenvalues μ4 of the covariance operator Cyy decay #4 S 1-1-
(EMB) For (p, 1), the inclusion map (Hg < [T)) is continuous and bounded by A.
16

---

Published as a conference paper at ICLR 2023
(SRC) F F [g] for 3 [1,2] (note that 3 < 1 would include the misspecified setting).
Lemma CA. Consider the well-specifee case of conditional expectation estimation (see Li et al.
2.22 For bounded kernels over X, Z, Y and a (B.p) -k-keeel over Y. F(y) = E [ Y (g),
bounded [| Cr, and M points used estimate F, define the conditional expectation estimate as
F(y) Kay (Kyy T) Kz..
(45)
where AM ((L/M&tP).
Then, the estimator 'Ir (xxxK22) (B 1)) of the "true" CIRCE estimator (i.e., with the actual conditional expectation) deviates from the tue value as Op 0/01/M/0-11/000001))
Proof. First, decompose the difference:
Tr (KxxKzz) - -Ir [Kxxk22 'r (Kxx (K2z K2z))
(46)
=Tr (Kxx (K22 R2z) 2 Krr]) - Tr Tr (Kxx @ Kyrl K22 - R22))
(47)
where in the last line we used that matrices are symmetric.
Let's concentrate on the difference:
[K2 K22), is (f(w)) F(U)), (((s)) + (f(us) - -F(s), v(zi))
(48)
+ (F(U)) F(y,)) - (E(v)): F(u,) = =F(j))
(49)
= -((()) - F(vi), v(zz)) + ( (F(ws) - F(yi), v((i))
(50)
+ (F(M) F(U)) F(w)) (F(w)), f(ws) -F()))
(51)
= (F(w.) - F(vi), F(U,) v(z))) + (F(U)) (((s)) F(v:)- ((2)))(z))))
(52)
As we're working in the well-specified case, by definition the operator E G. where g is a vector- valued RKHS (Li et al., 2022 Definition 1). This implies that for the function [K,h)(-)) K x) (where/ l E H,y).
(F(x), h) (F, Keh)g
(53)
We can now re-write the difference as
K2 Kíz) = (F (F- (F(u;) - - (21)) + K2, (F(U))-(Ez)))
(54)
We can use the triangle inequality and then Cauchy-Schware to obtain
(K2z - K22), is
$ $IF=- =f1=-Fll (IKm, (F(wn) - (1,))) + [K, (F(w)) ((t)))
(55)
= =IIF Fllg (k() y4 vs)l(F(())) (21))l + k(y, (())) - ((z))llue))
(56)
S C1 || رllo CC2 + Cs || flls)
(57)
for some positive constants C1 (since the kernels over both and y are bounded, F is bounded too and hence || < || As all kernels are bounded,
Fll + [F]]
Tr (Kxx Kyrl KS2 - (52--kzz)
< C.C.IFF - Àlle (C2+ CallF-lF--0 Flls)
(58)
B(B 1)
for positive constants C₁ C4.
17

---

Published as a conference paper at ICLR 2023
Now Theorem of Li al. (2022) with y 1 and À (11/M++)) which shows that
(IF TVKM
2-1 4e
(59)
for some positive constant K, which gives us the (p(1/M #1++0
deviation.
Now we can combine the two lemmas to prove Theorem 2.7
Proof of Theorem 2.7 Combining Lemma C.2 and Lemma
C.4 and using union bound, obtain
the (L(L/VB + 1/M zF+D) 1/MR)+
rate.
Corollary C.5. For B points and M holdout points, the CIRCE estimator
CIRCE
1 B(B - Tr (Rxx (Kyr 2 k2z))
Ā = A - diag(()
(60)
911 converges Op(L/VBBBBB.. + 1/M 2(7+8))
Proof. This follows from the previous two proofs.
Corollary C.6. For points and holdout points, the CIRCE estimator
CIRCE B(B-1) Tr (HKxxH (Krr K22)).
1
H I B
1nl
(61)
has bias of ())BB) and converges as (,(1/BB++))) 1/M B(tt))
Proof. This follows from the previous two proof's and the fact that K is centered matrix, meaning that in expectation HK K
This estimator can be less biased in practice, as K2z is typically biased due to conditional expecta- tion estimation, and H K H re-centers it.
D RANDOM FOURIER FEATURES
Random Fourier features (RFF) Rahimi Recht (007) allow to approximate a kernel k( x22) Rd
D EP (x( (I2)) and therefore K = RR
The algorithm estimate CIRCE with RFF provided in Algorithm We sample Do points every L iterations, but in every batch only use D of them to reduce computational costs. It takes 22 + D)M) compute WT and WT every L iterations. each iteration, it takes O(BD² + B)D) to compute CIRCE. Therefore, average (per iteration) cost of RFF estimation becomes O ae M + M + BD + BBD)).
E SYNTHETIC DATA AND ADDITIONAL RESULTS
We used Adam (Kingma & Ba 2015) for optimization with batch size 256, and trained the network for 100 epochs. For experiments on univariate datasets, the learning rate was le-4 and weight decay was 0.3; for experiments
multivariate datasets, the learning rate was 3e-4 and weight decay was 0.1. We implemented CIRCE with random Fourier features (Rahimi & Recht (007)) (see Appendix DD) of dimension 512 for Gaussian kernels. We swept over the hyperparameters. including RBF scale, regularization weight for ridge regression, and regularization weight for the conditional independence regularization strength.
All synthetic datasets are using the same causal structure as shown Figure I sweep is listed in Table and it is the same for all test cases.
Hyperparameters
18

---

Published as a conference paper at ICLR 2023
Algorithm 2 Estimation of CIRCE with random Fourier features
Holdout data {(2,, 1=) mini-batch { 24, 9:) Holdout data Leave-one-out (Theorem
for (ridge parameter) and By (parameters of Y kernel);
((x.) (KY I1
X, by = arg min Σ
(Kyr(Krr+A)) ").))
W1 =KKy + XI)
W2 W1
Every L minn-batches
Sample Do RFF R(-)
WT = R(Y) ((Y))WRR(O) W(R(Z), W = ( W2)(()
Mini-hatch
Use D random RFF out of Do
Compute R(y), R((z) (mini-batch)
K Kyy ① K== RI R(=)T -R())WFR())T) + R())ERR()
CIRCE B[B-I] Tr (HK,, -
Parameter
Values
CIRCE and HSCIC
GCM
conditional independence ridge regression À RBF scale
log space between [1, 104]: log space between [10-2 10-00.5
{ 0.001, 0.01, 0.1, 1}
{ 0.001, 0.01, 0.1,
Table 2: Hyperparameters for CIRCE, HSCIC and GCM on synthetic datasets.
E.1
UNIVARIATE CASES
Structural causal model for univariate case
Y,ez N(O, 1)
6A, ~ (.0,0.1)
Z = Y +
= 0.5Zca + 2Y
B 0.5 exp AY) sin() + 57 + 0.2cB
Structural causal model for univariate case 2:
Y,cz ~ (00
CA,EB N(0,0.1)
Z Y +ez
A exp(- -0.552 sin 27 + +-2Y+0024 +.266
B sin(22 exp( -0..AAY) 5Z 0.2cB
19

---

Published as a conference paper at ICLR 2023
E.2 MULTIVARIATE CASES
Structural causal model for multivariate case I:
Y,ez, NO0, 1)
6A ~ (0,)
Z; y +
4 = exp(-0.52,) +
Σ Zi sYn + 0.1cA
B = cxp(-0.52z)
Σ
Z+) + AY + 0.1cg
Structural causal model for multivariate case 2:
Y2,E NO
CA ~ 0.1)
== Y- +
A = exp( -0.52) + sin
Y,Z + 0.1eA
B exp(=0.52) + Σ
Yi + Z + AY1 0.1eB
F IMAGE DATA DETAILS
A. OIRCE
B. HSOIC
C. GCM
0.150
n-domain
0.150
In dodadan
0.125
DOG
000
0.125
trained 900
DOp
0.125
0.100
88
0.100
loss
0.300
MSE
0.075
mremed GDD
0.050
0.050
0.050
0.025
0.025
0.025
0.000
0.000
0.000
10c
100
1.07
10
10:
10a
10
10-2
10-1
100
regularization strength Y
regularization strength
regularization strength
Figure 7: dSprites with nonlinear dependence. CIRCE used holdout data in training. Blue: in- domain test loss; orange: out-of-domain loss (OOD); red: loss for OOD-trained encoder. Solid lines: median over 10 seeds; shaded areas: min/max values.
For both dSpritres and Yale-B, we choose the following training hyperparameters over the validation set and without regularization: weight decay (Ie-4, 1e-2), learning rate (le-4, 1e-3, 1e-2) and length of training (200 or 500 epochs). These parameters are used for all runs (including the regularized ones). For dSprites the batch size 1024. For Yale-B the batch size 256. The results for both standard (Corollary CC.) and centered (Corollary C.6) CIRCE estimators were similar for dSprites stable for Yale-B (the reported
(the reported one is standard), but the centered version one is centered). This is likely due to the bias arising from conditional expectation estimation. For dSprites, the training set contained 589824 points, and the holdout set size was 5898 points. For Yale-B, the training set contained 1 11005 points, and the holdout set size was 1267 points.
All kernels were Gaussian: k(2,x') [1.0,0. 0.1, 0.01, 0.001] and ridge regression parameter from [0.01, 0.1, 1.0, 10.0, 100.0j. The other two kernels had x² 0.01 for linear and y-cone dependencies; for the nonlinear case, the kernel over 7 had x² = 1 due to a different scaling of the distractor in that case.
exp(-122 |z x' 2/112/ /202))
For Y. o² from
We additionally tested a setting in which the M holdout points used for conditional expectation estimation are not removed from the training data for CIRCE. As shown in Figure 7 for dSprites with non-linear dependence, this has little effect on the performance.
20


Reviews:
[{"review_id": "juP7o8MXGme", "reviewer": "Reviewer_ZZGR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a new measure of conditional independence for multivariate continuous variables, based on the equations of  Daudin, 1980. Although previous tests have also used other equivalent forms of equations from (Daudin, 1980), the proposed  CI measure and statistic seem to enjoy the advantage of avoiding minibatch computation involving $Z$ and $Y$. Finite sample estimate with convergence guarantees and strategies for efficient estimation from data are also provided.", "summary_of_the_review": "I'm kind of between weak rej and wek acc. The method shows some usefulness in experiments and has good theoretic characterizations. On the other hand, it does not provide an intuitive sense of why it could be better. I wait for authors response before recommending an acceptance.", "strength_and_weaknesses": "Pros:\n\n- a new CI meansure with finite sample estimate with convergence guarantee\n- the method is shown useful in some experiments\n- writing is good (expect for several places where notations are not defined in the main text)\n\nCons:\n\n- except for avoiding minibatch computing of $Z$ and $Y$, it is not clear what other benefits the proposed statistic could provide.\n- the experiments are somewhat toy and the results are mixed ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "dNlnmyBrld", "reviewer": "Reviewer_FXBx", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a measure of conditional independence called CIRCE that can be used as a regularizer in a large-scale mini-batch training. The key idea of CIRCE is that the conditional independence holds if and only if Eq. (4) holds, so we can measure the conditional dependence by how much the equation is violated. However, the equation must be checked for all functions g and h of the $L^2$ spaces, which is not directly tractable. The authors rewrite this condition by replacing the $L^2$ spaces with RKHSes, which reduces the equation to the norm of one single operator being zero (Eq. (10)). The estimation of the operator can be decomposed into the one related to the encoder and the other that does not depend on the encoder but requires a conditional expectation estimation. Conveniently, the regression part can be done beforehand and does not have to be calculated for each mini-batch. The authors prove the consistency with a rate of convergence of the proposed estimator and provide experiments on learning causal relationships using synthetic data and real image data.", "summary_of_the_review": "The authors made great contributions to incorporating a conditional independence regularization in mini-batch training with a novel and interesting approach. They prove correctness in theory and confirm the effectiveness by experiments and provides many insights. I suggest accepting this paper.", "strength_and_weaknesses": "# Strengths\n- The authors point out that Eq. (4) has a nice property that is useful for mini-batch training.\n- They provide a clever way of estimating it using RHKSes.\n- They prove the correctness of the proposed method.\n- The experiments are interesting and demonstrating the effectiveness of the proposed method.\n\n# Weakness\n- I suppose that the paper claims the proposed method is computationally efficient, but I could not find any analysis or empirical results supporting it. In fact, Theorem 2.7 suggests that we want M to be large enough to compensate the slow rate, but calculating the kernel matrices may not be scalable in $M$.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DIv6yAiJoOA", "reviewer": "Reviewer_QXAF", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors study learning conditionally invariant representation of inputs $X$ such that conditional on label $Y$, the representation $\\varphi(X)$ and the distractor $Z$ are independent. This problem is motivated by broad applications in fairness, domain invariant learning, causal representation learning, etc. \n\nA challenge in enforcing conditional independence is that it is hard to measure conditional independence, effectively reducing the sample size if we naively split the data according to values of $Y$. A major contribution of this paper is reducing conditionally independent representations to marginally independent representations, based on a result of [1]. Then the authors proceed, by invoking reproducing kernel Hilbert space, to transform the problem into an equivalent statement (Thm 2.5) in which we look for a CIRCE operator such that its Hilbert-Schmidt norm is zero. On finite-sample data, an estimator of the CIRCE operator is given, so this effectively becomes a regularizer.\n\nThe authors then present several numerical simulations and data analysis, demonstrating the advantages of the proposed CIRCE method with existing approaches in the literature.\n\n\n\n\n[1] JJ Daudin. Partial association measures and an application to qualitative regression.", "summary_of_the_review": "The authors proposed a new measure called CIRCE for enforcing conditional independence, and this measure can be efficiently computed from data. Overall I believe this is a good paper, and thus I recommend acceptance of this paper.", "strength_and_weaknesses": "Learning conditionally invariant representation is a very important problem that has the potential to solve a wide of issues in machine learning, such as distribution shift, spurious correlation, racial bias from datasets, etc. The authors consider a quite general setup where one seeks to convert the hard-to-measure conditional independence into a manageable form.\n\nThe major strength of this paper is a new measure that can be efficiently computed from data. This measure involves marginal independence between $X$ and $(Y,Z)$ under square-integrable functions, thus cleverly separating the computation of (potentially high-dimensional) inputs $X$ from $(Y,Z)$. \n\nAlso, the empirical evaluation seems to favor this CIRCE method when compared with existing methods. This suggests that the proposed approach has good potential impact.\n\nA weakness of this paper, partly due to the limit of the paper length, is a lack of analysis of the statistical efficiency (or power in statistical tests).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%