Structure-agnostic Causal Representation Learning

1 Introduction

• Structure-based methods require explicit DAGs and complete SCMs, while distribution-invariant methods commit to a fixed invariance that can discard predictive signal when the commitment is wrong.These approaches are presented as barriers when the causal structure is unknown.Source: §1 · p. 1
• The clinical example distinguishes symptoms, biomarkers, and vital signs as anti-causal, confounded-descendant, and confounded-outcome variables, respectively, whose structures are unknown to the learner.The paper uses this example to motivate discovering each variable’s causal pattern rather than assuming one structure for all variables.Source: §1 · p. 1
• Existing methods require manual causal-type partitioning, which is error-prone and computationally costly, and lack guarantees when structure identification is uncertain.The stated search cost is O(mk) evaluations for m structures over k variable subsets.Source: §1 · pp. 1–2
• Different causal structures require incompatible invariances, so a representation optimized for one may perform poorly under another.The paper frames the goal as learning invariant representations without knowing the causal structure in advance.Source: §1 · p. 2
• SaCRL uses a SoftMin objective over invariance violations to concentrate on the correct structure, with guarantees for structure identification, invariance violation, and out-of-distribution generalization.The identification guarantee also holds under random-feature approximation of HSIC.Source: §1 · p. 2

2 Background

• The paper uses uppercase letters for random variables, lowercase letters for realizations, and calligraphic letters for spaces; ⊥⊥ denotes unconditional or conditional independence.Expectations, indicators, and set cardinality also receive standard notation.Source: §2 · p. 2

2.1 Measure Theory

• The paper follows ACIA [7] in using measure-theoretic probability and directs readers to Appendix C.1 for formal definitions.The referenced foundations include measurable spaces, probability measures, product spaces, σ-algebras, and Markov kernels.Source: §2.1 · p. 2

2.2 Canonical Causal Structures

• Structure-agnostic refers to eliminating the learner’s need to know the true structure beforehand, not searching over every possible structure.Figure 3 distinguishes G1 by Y → X, while G2 and G3 have X → Y and confounding paths.Source: §2.2 · pp. 2–3
• Under partial observability and environment changes acting through latent confounders, the X–Y relationship falls into anti-causal G1, confounded-descendant G2, or confounded-outcome G3.The paper treats these three structures as exhaustive under those conditions; an unconfounded X → Y case is included in G2 with zero confounder influence.Source: §2.2 · pp. 2–3

3.1 Motivation

• In a confounded-descendant setting, enforcing anti-causal invariance can remove environment-varying information that carries the causal X → Y signal.The paper contrasts an achievable correct invariance that preserves prediction accuracy with incorrect invariances that require discarding predictive information.Source: §3.1 · p. 3

3.2 Problem Setup

• The learner observes datasets from m ≥ 2 environments, each generated by an unknown joint distribution Pₑ(X, Y).The data-generating structure is one of G1, G2, or G3, but is unknown to the learner.Source: §3.2 · pp. 3–4

3.1 Motivation

• Anti-causal settings require ϕ(X) ⊥⊥ E | Y, confounded-descendant settings require Y ⊥⊥ E | ϕ(X), and confounded-outcome settings require ϕ(X) ⊥⊥ E.The representation maps X into a latent space Z.Source: §3.1 · p. 3, §3.2 · p. 4

3.2 Problem Setup

• The task is to identify the true structure, find a representation satisfying its corresponding invariance, and learn a predictor with optimal out-of-distribution generalization.These objectives are pursued simultaneously.Source: §3.2 · p. 4
• The joint objective selects a structure, learns its invariant representation, and optimizes worst-case risk across environments.Its formulation presents discrete structure selection and a non-differentiable indicator as challenges.Source: §3.2 · p. 4
• Because each invariance is an independence statement, kernel independence testing provides a continuous measure for addressing the discrete, non-differentiable selection problem.The formulation uses violation metrics to quantify whether candidate invariances hold.Source: §3.2 · p. 4

4 Kernel Independence Framework

• For characteristic kernels, HSIC completely characterizes statistical independence, making its norm a dependence measure.The paper names Gaussian and delta kernels as examples.Source: §4 · p. 4
• Empirical HSIC estimates dependence from finite samples using kernel matrices and a centering matrix.The matrix entries are kernel evaluations on the observed samples.Source: §4 · p. 4
• Kernel regression residuals remove dependence on Z, allowing conditional independence to be tested by applying standard HSIC to the residualized variables.The residuals are defined as observed values minus their estimated conditional means.Source: §4 · pp. 4–5
• Under additive noise, suitable characteristic bounded Lipschitz kernels, and L2-consistent regression estimates, conditional independence is equivalent to residual independence and conditional HSIC is consistent.The paper states that its conditional-HSIC-based violation metrics correctly detect whether their corresponding invariances hold under this model.Source: §4 · p. 5

5 Structure-agnostic Causal Representation Learning (SaCRL)

• Testing I1, I2, and I3 requires variation in P(X|Y), P(Y|X), and P(X), respectively.The paper identifies these as the environment-diversity conditions for distinguishing the three candidate structures.Source: §5 · p. 5

5.1 Structure Violation Metrics

• Three structure-specific violation functions use HSIC to measure dependence patterns associated with the anti-causal, confounded-descendant, and confounded-outcome structures.The empirical measures use residuals from kernel ridge regressions where conditioning is required.Source: §5.1 · p. 5
• Population violations support the theory, while the algorithm optimizes empirical violations whose consistency is needed to connect training to those guarantees.The empirical quantities are computed from pooled observations across environments.Source: §5.1 · p. 5

5.2 Soft Structure Selection

• SoftMin provides a differentiable relaxation for jointly selecting structure and learning a representation from candidate violation metrics.The framework also defines adaptive weights for each structure given the representation.Source: §5.2 · p. 5

5.3 Unified Objective Function

• The distributionally robust objective uses CVaR across environments; ρ=0.5 averages the worst half in practice, while ρ=1/|E| is used for theory.CVaR is convex and has a closed-form subgradient.Source: §5.3 · p. 6
• Training uses a single-loop relaxation, multiple random starts, and temperature annealing; the identified structure is the post-training hard argmin of empirical violations.The guarantees concern the converged representation because conditioning targets move during training; the authors report stabilization from warm starts, annealing, and cross-fitted residuals.Source: §5.3 · p. 6
• Random Fourier features reduce empirical HSIC cost to O(nD^2) time and O(nD) memory, versus O(n^2) time and memory for exact HSIC.With D=Ω(κ^4η^-2d log(n/δ′)) features, the stated structure-identification guarantee holds with probability at least 1−6 exp(−nη^2/(8192κ^4))−δ′.Source: §5.3 · pp. 6–7
• The heterogeneous extension assigns structures per feature, with per-feature identification guarantees and sample cost scaling as O(d).It also uses a calibrated permutation threshold to control false positives for features assigned to ⊥.Source: §5.3 · p. 7

6 Theoretical Guarantees

• Violation characterization shows that the correct structure is identifiable.The paper also establishes representation optimality and out-of-distribution generalization bounds.Source: §6 · p. 7
• Finite-sample structure identification holds under random-feature approximation.The paper identifies this result as Corollary 1.Source: §6 · p. 7
• The theoretical results include representation optimality.Source: §6 · p. 7
• The theoretical results include out-of-distribution generalization bounds.Source: §6 · p. 7

7.2 Experiment 1: Structure Identification

• Identification reaches at least 95% at n=5000 and at least 89% at n=2000; semi-synthetic benchmarks select the correct structure in 75–95% of runs.G3 is identified most reliably; G2 is most challenging in small samples because it requires estimating conditional independence.Source: §7.2 · p. 8, Table 1 · p. 8, Table 2 · p. 8

7.3 Experiment 2: OOD Generalization

• On Colored MNIST, SaCRL identifies G1 in 92% of runs and reaches 45.2% OOD accuracy, +18pp over ERM.IRM’s wrong-structure invariance falls below ERM, while CIRCE’s fixed penalty does not overcome the color shortcut under the shared training budget.Source: §7.3 · p. 8, Table 3 · p. 8

7.4 Experiment 3: Structure Analysis on PACS

• On PACS, different structures are selected across splits, but p < 0.05 on every split indicates the selected structure is the closest canonical one, not an exact fit.Seed agreement is 5/5 on three splits with margin at least 0.28 and 4/5 on Cartoon, which has the smallest margin.Source: §7.4 · p. 9, Table 4 · p. 9

7.5 Experiment 4: Domain Generalization on DomainBed

• SaCRL achieves the best per-domain and average accuracy on all three benchmarks, with average improvements over +2.1pp on PACS, +4.2pp on VLCS, and +3.1pp on OfficeHome.Fixed-invariance baselines show no consistent improvement.Source: Table 5 · p. 9, §7.5 · p. 9

7.6 Experiment 5: Robustness to Misspecification and Limited Diversity

• At ν=0.50, no candidate invariance holds and SaCRL’s weights remain spread; its soft model average exceeds ERM by 12.7pp.SaCRL outperforms every evaluated baseline in each setting, and its gain over ERM persists at δmin=0.05.Source: §7.6 · pp. 9–10, Table 6 · p. 10

7.7 Ablation Studies

• Replacing SoftMin with hard selection lowers identification accuracy from 89.0% to 79.5%.Noisy early violation estimates can trigger premature commitment; reliable identification is reported with at least three training environments, while two are unstable.Source: §7.7 · p. 10, Table 7 · p. 10

8 Conclusion

• SaCRL recovers true structures on synthetic and semi-synthetic Bayesian-network benchmarks and remains robust under bidirectional dynamics and limited environment diversity.It uses soft optimization over HSIC-based invariance violations, with SoftMin aggregation and RFF-based HSIC approximations; its guarantees cover structure identification, invariance satisfaction, and OOD generalization.Source: §8 · p. 10

A Related Work

• Existing methods assume causal graphs, hardcode structural invariances, or decouple structure discovery from representation learning; SaCRL jointly optimizes predictive performance and structure-adapted representations.Its adaptive weighting evaluates candidate structures and concentrates on the correct one.Source: A Related Work · p. 19

C.4 Measure-Theoretic Causality

• The structure-agnostic causal space extends product causal spaces with structure-indexed causal-kernel families for candidate causal DAGs.These kernels encode how interventions propagate under each candidate structure.Source: §C.4 · p. 22

C.6 Assumptions

• The Lipschitz condition controls prediction-error propagation under distribution shift and appears directly in the generalization bound.This condition is referenced in Theorem D.5.Source: §C.6 · p. 24
• The representation class is assumed compact and convex, continuously differentiable in its parameters, and to have smooth violation functions, conditions described as standard for neural networks.These regularity conditions ensure convergence of gradient-based optimization.Source: §C.6 · p. 24
• Before training, test each estimated conditional-mean-embedding column against a permutation null, remove the corresponding structure if insignificant, and use ERM if no column is significant.The tested columns map to structures as j=1: G3, j=2: G1, and j=3: G2; the passages state that environments then carry no information about structure.Source: §C.6 · p. 24

D.1 Violation Characterization, Structure Identification & Representation Optimality

• Predictive representations achieve zero violation for the true structure but at least η/2 for incorrect structures, enabling consistent finite-sample identification.Under the identification theorem’s conditions, the adaptive weight on the true structure approaches 1 as sample size grows.Source: §D.1 · pp. 24–25
• With expressive classes, the global minimum achieves exact true-structure invariance and Bayes risk; stronger regularization can reduce violation at the cost of prediction accuracy.For finite samples, violation decreases at O(n^-1/2).Source: §D.1 · p. 25

D.2 Generalization Bounds

• The generalization bound separates training error, distribution shift, and estimation error, and the true-invariance violation contributes directly to generalization error.The shift penalty depends on the interventional kernel distance to the nearest training environment.Source: §D.2 · p. 26

D.3 Sample Complexity

• Theorem D.6 specifies the per-environment sample size required for structure identification with probability at least 1 − δ and generalization error at most ϵ.The bound depends on the representation class’s covering number.Source: §D.3 · p. 26

E Proofs

• The proofs establish supporting concentration and regression-consistency results for empirical HSIC and kernel ridge regression.The kernel-regression result uses regularization γ = n^-1/(2+d), where d is the effective dimension.Source: E Proofs · pp. 26–27

E.1 Proof of Lemma 1 (HSIC Characterizes Independence)

• With characteristic product kernels, HSIC is zero exactly when the variables are independent.The proof relates HSIC to the squared maximum mean discrepancy between the joint distribution and the product of its marginals.Source: §E.1 · p. 28

E.2 Proof of Lemma 2 (Conditional HSIC Consistency)

• Residual-based conditional HSIC converges to zero under conditional independence and to a positive value otherwise.The result uses consistent estimates of the conditional means and the equivalence between residual independence and conditional independence.Source: §E.2 · p. 28

E.3 Proof of Lemma 3 (SoftMin Properties)

• The SoftMin proof establishes bounds, limiting behavior, and a gradient expression for the aggregation.It treats a unique minimizing structure directly and extends the result to ties by continuity.Source: §E.3 · pp. 28–29

E.4 Proof of Theorem D.1 (Violation Characterization)

• Graph d-separation and faithfulness turn candidate invariance constraints into zero or positive violation scores, establishing achievability and non-achievability.The proof uses the Markov property and faithfulness, with Lemmas 1 and 2 connecting independence to zero violation and dependence to positive violation.Source: §E.4 · p. 29

E.5 Proof of Theorem D.2

• 1−6 exp(−nη^2/(2048κ^4) identifies the true structure with probability at least that bound under Assumptions 2–6.The proof separates the true structure's violation from alternatives by the faithfulness gap η, then applies a union bound over three candidates.Source: §E.5 · pp. 29–30

E.6 Proof of Corollary 1

• D = Ω(κ^4η^−2d log(n/δ′)) random Fourier features are specified for approximation error εD = η/(16Cκ^2), with probability 1−δ′.The bound splits the tolerance between sampling and approximation error.Source: §E.6 · p. 30

E.7 Proof of Theorem D.3

• Under Assumptions 2–6 and λ > 0, Theorem D.3 analyzes the learned representation's true-structure invariance through the regularized objective.The proof links the SoftMin gradient to the true-structure violation as the adaptive weight on that structure approaches 1.Source: §E.7 · p. 30

E.8 Proof of Theorem D.4 (Global Optimality)

• At a global minimum, the true-structure violation is zero and the prediction loss equals Bayes risk when the classes contain an exactly invariant representation and Bayes-optimal predictor.A positive violation would allow replacing the representation with an invariant sufficient one, reducing the SoftMin term without worsening prediction loss.Source: §E.8 · p. 31

E.9 Proof of Theorem D.5 (Generalization Bound)

• R_test(w_n ◦ ϕ_n) − R_e*(w_n ◦ ϕ_n) ≤ L_w · d_K(e_test, e*) + C_η · V_k*(ϕ_n), while Corollary 3 proves convergence in probability to oracle risk.The bound separates distribution shift from residual invariance violation; the asymptotic result identifies the oracle risk over Φ_k*.Source: §E.9 · p. 32, §E.10 · p. 33

E.11 Proof of Theorem D.6 (Sample Complexity)

• 1−δ probability suffices for both successful structure identification and generalization error at most ε under the combined sample-complexity requirements.The proof combines the identification bound with the generalization and violation requirements.Source: §E.11 · pp. 33–34

E.13 Proof of Theorem F.1 (Algorithm Convergence)

• The analysis establishes stationarity and weight concentration, and bounds the true-structure violation V_k*(ϕ_T) by 1/(2L_V)‖∇V_k*(ϕ_T)‖² = O(λ⁻²)·O(T⁻¹/²) = O(T⁻¹/²).Source: §E.13 · p. 36

E.14 Proof of Theorem G.1 (Heterogeneous Structure Identification)

• With high probability, the tested violation is at least 3η(j)/8 and exceeds its permutation-calibrated threshold.Under the null, all three violations are positive, while the permutation null distribution of HSIC concentrates around zero, yielding a valid threshold.Source: §E.14 · pp. 36–37

F Algorithm Details

• The appendix presents the complete optimization procedure through its main algorithm, subroutines, complexity analysis, and convergence guarantees.The stated scope includes the structure-agnostic representation-learning algorithm and its supporting analysis.Source: F Algorithm Details · p. 37

F.1 Main Algorithm

• The structure-agnostic learning problem admits a bi-level decomposition, and CVaRρ is convex and subdifferentiable.Algorithm 1 is run from at least 10 initializations, with the final model selected as described in Section 5.3.Source: §F.1 · p. 37

F.2 Subroutines

• For shift-invariant kernels, F.2 defines random Fourier features and refers to Algorithms 2–4 for the subroutines.The listed subroutines cover structure violations, kernel-regression residuals, and RFF-HSIC computation.Source: §F.2 · p. 37, §F.3 · pp. 38–39

F.3 Complexity Analysis

• |E| · B · (dx + dz) + ND^2 + N^3 gives the per-iteration cost; total cost is linear in candidate structures.The ND^2 RFF-HSIC and N^3 kernel-ridge terms depend on minibatch size N rather than dataset size; one Cholesky factorization per conditioning variable is shared across regression targets.Source: §F.3 · p. 37

F.4 Convergence Guarantees

• Algorithm 1 achieves O(T^-1/2) stationarity and true-structure violation, while α(T)_k* ≥ 1 − 2 exp(−βTη/2) under the stated step-size and annealing schedules.The ERM initialization begins in the predictive region with ε = O(n^-1/2), avoiding degenerate solutions with trivial prediction accuracy.Source: §F.4 · p. 39

G Extension to Heterogeneous Structures

• The heterogeneous extension assigns each feature to G1, G2, G3, or ⊥ and bounds false-positive assignment probability by α for features with no applicable canonical structure.Its generalization result extends the stated bound with a per-feature structure-estimation error.Source: G Extension to Heterogeneous Structures · pp. 39–40

H.1.1 Hyperparameter Selection

• Table 9 provides defaults and selection guidance for λ, β, γ, D, and ρ.The passages name the parameters but do not specify the table's recommended values.Source: §H.1.1 · p. 40, Table 9 · p. 40

H.1.2 Numerical Stability

• Numerical safeguards add 10^-6 to kernel-matrix diagonals, clip βV_k to [−20, 20], and normalize HSIC by its empirical standard deviation.Source: §H.1.2 · p. 40

H.1.3 Kernel Selection

• The implementation uses Gaussian RBF kernels for representations, delta kernels for classification labels and discrete environments, and Gaussian RBF kernels for regression labels.Source: §H.1.3 · p. 41

H.2 Synthetic DGP Equations

• Synthetic data use three environments and ten features for each canonical structure, with environment-varying noise for G1 and G3 and varying confounder means for G2.Weight matrices are sampled from N(0, 0.52) and fixed across runs.Source: §H.2 · p. 41

H.3 Hyperparameter Sensitivity Results

• Across the sensitivity sweep, λ variation changes accuracy by at most about 5 percentage points in the hardest settings, while βmax variation is at most 2.5 points.When ν = 0.75, all configurations reach about 99.5%; the authors recommend λ ∈ [1.0, 5.0] and βmax = 50.Source: Table 10 · p. 41, Table 11 · p. 41, §H.3 · p. 41

H.5 Margin Calibration

• Identification accuracy increases monotonically with the weight margin, while the crossover experiment compares SoftMin with hard arg min_k V_k selection across ν values.The margin measures how strongly the data support the selected structure; the crossover spans G2 (ν = 0) to G1 (ν = 1).Source: §H.5 · p. 41, §H.4 · p. 41, Table 13 · p. 42

H.6 Semi-Synthetic Bayesian-Network Benchmarks

• Five semi-synthetic benchmarks span two structures across three networks, so a single-structure default is correct on at most 3/5; the two G3 benchmarks come from different networks.Benchmarks were retained only when competing-invariance violation exceeded 5.0 standard deviations of the permutation null; SACHS and ASIA required adjustments.Source: §H.6 · p. 42

H.7 Cross-Fitting Variant

• Cross-fitting and joint residualization yield OOD accuracies of 73.9 and 74.0, respectively; both variants outperform ERM by about 13 percentage points.The cross-fitting comparison uses the bidirectional DGP at ν = 0.5 with 1,000 samples per environment; EMA conditioning results are nearly unchanged.Source: Table 14 · p. 42, §H.7 · p. 42, Table 15 · p. 43

H.9 RFF Approximation Error

• RFF-based HSIC approximation error falls from 1.42 × 10^-3 at D = 100 to 4.4 × 10^-4 at D = 2000 on synthetic data with n = 2000.Source: Table 16 · p. 43, §H.9 · p. 43

H.10 Effect of the Number of Training Environments

• With two environments, structure identification is unstable; three or more yield at least 89% identification and 84% OOD accuracy, with diminishing returns beyond four.The two-environment setting lacks contrast to test three invariances; the results are for synthetic G2 data with n = 2000.Source: Table 17 · p. 43, §H.10 · p. 43

H.11.1 Training Time and Memory

• With D = 1000 RFF features, SaCRL adds about 30% training overhead over ERM while avoiding exact HSIC's O(n^2) complexity.For 10K Colored MNIST images, exact kernel matrices would require more than 10 GB of GPU memory and four times the training time; RFF has negligible accuracy loss. Table 19 breaks down per-epoch PACS runtime.Source: §H.11.1 · p. 43, §H.11.2 · p. 43, Table 18 · p. 44

• The framework does not cover cyclic systems, multi-confounder dynamics, or settings where the environment directly rewires X–Y; identification requires sufficient environment diversity and at least three training environments.When the minimum violation exceeds the permutation threshold, the data do not support a canonical structure, so the selected structure should not be interpreted as identified.Source: I Limitation · p. 44

• Unlike prior causal-representation results that take generative structure as an analyst-supplied assumption, SaCRL identifies among three canonical structures from multi-environment data.Source: J Applications and Broader Connections · p. 45
• For bidirectional human–AI influence, SaCRL keeps structure weights spread rather than committing to one of three canonical structures; feedback cycles remain outside that candidate set.Source: J Applications and Broader Connections · p. 45
• For clinical prediction, a permutation test flags when none of the three canonical structures fits, and the heterogeneous extension assigns structures per variable.Source: J Applications and Broader Connections · p. 45
• 45.2% for SaCRL versus 21.3% for IRM and 27.2% for ERM on anti-causal Colored MNIST; IRM’s fixed covariate-shift invariance underperforms ERM.Source: J Applications and Broader Connections · p. 46
• When sensitive attribute A acts as environment E, SaCRL maps independence, separation, and sufficiency to I3, I1, and I2, respectively; criterion choice remains normative.Source: J Applications and Broader Connections · p. 46
• SaCRL’s diversity matrix measures marginal, conditional, and outcome shifts across training environments; a pretraining permutation check identifies which invariances are testable.Source: J Applications and Broader Connections · p. 46
• 75–95% of runs select the graph-fixed structure on ASIA, ALARM, and SACHS semi-synthetic benchmarks; SaCRL learns representations while testing their invariances.Source: J Applications and Broader Connections · p. 46