1 Introduction↩︎

Machine learning models often exploit spurious correlations that hold in training data but fail under distribution shift [1]. This issue appears in several related forms, where models must detect inputs outside the training distribution [2]–[5], and co-occurrence bias in image classification, where models may rely on unstable correlations among classes rather than class-specific evidence [6]–[11]. Invariant learning uses multi-environment data to target features whose predictive relation with the label is stable across environments [12], [13]. Theory shows that such invariant structure can be statistically identifiable under diversity assumptions [14], yet empirically, invariant methods sometimes help and sometimes do not [15], [16]. We ask whether this inconsistency can arise even in idealized settings where invariances are identifiable.

We answer yes by establishing a computational–statistical separation for spurious correlation removal. Under a black-box samplable supervised sparse recovery primitive, motivated by average-case sparse-recovery reductions but not claimed to follow directly from existing Planted-Clique-to-sparse-CCA reductions, we construct samplable multi-environment instances where the predictive invariant direction is identifiable as the unique maximizer of an invariance–predictivity population score and is recoverable with polynomially many samples by exhaustive (exponential-time) search, but any polynomial-time constant-accuracy recovery algorithm at comparable sample sizes would contradict the primitive (Theorem 6). The construction maps the black-box sparse primitive to labeled multi-environment samples without accessing the hidden support.

A second message is that the number of environments matters less than their diversity. We quantify diversity by a separation parameter \(\gamma\) measuring how differently environments perturb spurious correlations (Definition 2). When \(\gamma=0\) (i.e., environments do not induce distinguishable variation in spurious conditional means), the invariant subspace can be unidentifiable even with unlimited data (Corollary 1). When \(\gamma>0\) and the environment-induced spurious shifts are sufficiently directionally rich (Proposition 10), recovery becomes possible and the required sample size decreases as diversity increases; in a structured label-induced shift regime the critical scaling is proportional to \(1/\gamma^2\) (Theorem 16). This predicts that a few diverse environments can be more informative than many similar ones.

We make four contributions. First, under a black-box samplable supervised sparse-recovery primitive, we construct samplable multi-environment instances exhibiting a computational–statistical gap for invariant subspace recovery. Second, we quantify environment diversity through a separation parameter \(\gamma\) and relate it to identifiability, minimax risk, and sample-complexity transitions. Third, we identify structural conditions under which polynomial-time methods achieve near-optimal rates. Finally, experiments on synthetic and standard spurious-correlation benchmarks illustrate compute–sample tradeoffs, diversity dependence, and practical diagnostics. Our hardness results are worst-case and conditional; the framework suggests estimating environment diversity before attributing invariant-learning failures to optimization or algorithmic limitations.

1.0.0.1 Conflict of Interest Disclosure.

The authors declare that they have no financial conflicts of interest related to this work. In particular, this paper does not evaluate any model, dataset, product, or service developed by an organization that financially supports or employs any of the authors in a way that would constitute a conflict under the ICML peer-review ethics guidelines.

2 Problem Formulation↩︎

We model spurious correlation removal as invariant subspace recovery from multi-environment data, focusing on a linear-Gaussian setting. For a subspace \(V\subseteq\mathbb{R}^d\), let \(P_V\) be the orthogonal projector and \(\mathrm{Gr}(k,d)\) the Grassmannian of \(k\)-dimensional subspaces.

Under Assumption 1, the environment-invariance of \(\mathbb{P}_e(Y\mid X_{\mathrm{inv}})\) means that the conditional law of \(Y\) given \(X_{\mathrm{inv}}\) is identical across environments. In the statistical analysis (Section 4) we add the standard linear-Gaussian structural assumption that \(Y=\langle w^*,X_{\mathrm{inv}}\rangle+\epsilon\) with \(w^*\in V_{\mathrm{inv}}\).

We quantify cross-environment variation in spurious features by a separation parameter.

Let \(n_e\) be the sample size in environment \(e\), \(N:=\sum_{e\in\mathcal{E}}n_e\), and \(n_{\min}:=\min_e n_e\). In the balanced case, \(n_e=n\) and \(N=n|\mathcal{E}|\).

2.0.0.1 Goal and metrics.

Given samples from all environments, recover \(V_{\mathrm{inv}}\). We evaluate estimators \(\hat{V}\) using the subspace distance \(\mathop{\mathrm{dist}}(V,V'):=\|P_V-P_{V'}\|_F\); for axis-aligned subspaces we also report feature selection accuracy (fraction of true invariant coordinates among the selected top-\(k\)).

3 The Computational-Statistical Gap↩︎

We show that spurious correlation removal can be statistically feasible yet computationally intractable in a conditional black-box sense. The computational lower bound in this section is for a samplable multi-environment wrapper around a supervised sparse recovery primitive, while the linear-Gaussian statistical theory is developed separately in Section 4.

Hypothesis 3 is included as motivation for average-case sparse-recovery hardness. The formal lower bound below is conditional on the black-box supervised sparse recovery primitive in Hypothesis 4; the key requirement for our reduction is samplability, namely that samples can be generated in randomized polynomial time from the primitive input without using the hidden sparse direction or its support.

3.1 A Black-Box Samplable Supervised Sparse Primitive↩︎

We use a standard average-case hardness template: planted-clique-based reductions motivate sparse predictive recovery tasks, such as sparse CCA and related problems. In the main reduction below, we use a supervised sparse recovery primitive as a black-box hardness assumption; Appendix 14 discusses its relationship to standard sparse CCA reductions and the scalar-response caveat.

3.1.0.1 Black-box status and learner access.

Hypothesis 4 is a conditional primitive. It is motivated by average-case sparse-recovery and sparse-CCA reductions, but we do not claim that it follows directly from existing Planted-Clique-to-sparse-CCA results. In particular, it is not the exposed scalar covariance model \(\mathrm{Cov}(Z,Y)=\lambda v\), which can be easy by empirical covariance estimation in some regimes. The empirical version of the score \(\Phi_P\) is part of the primitive interface used by the exhaustive-search learner. Equivalently, the primitive specifies a statistically estimable predictive criterion whose population maximizer is the hidden sparse direction. The reduction in Section 3.2 does not assume access to the hidden support or hidden direction; it only uses samples generated by the primitive and the empirical score estimator guaranteed by Hypothesis 4(iii). Therefore the hardness statement should be interpreted as a black-box transfer result for any supervised sparse-recovery task satisfying this interface.

3.2 Embedding into Multi-Environment SC Instances↩︎

We wrap the supervised sparse primitive into an SC instance. The constraint is that the resulting instance must satisfy Definition 1, in particular the invariance condition (C1).

3.2.0.1 Invariance–predictivity score over one-dimensional subspaces.

For a candidate one-dimensional subspace \(V\in\mathrm{Gr}(1,d)\), let \(u_V=(u_Z,a)\) be any unit vector spanning \(V\), where \(u_Z\in\mathbb{R}^{d_Z}\) is the primitive block and \(a\in\mathbb{R}\) is the spurious block. If \(u_Z\neq 0\), write \(\bar u_Z=u_Z/\|u_Z\|\); if \(u_Z=0\), set the predictive score below to zero. We define the predictive component inherited from the supervised sparse primitive by \[A(V):= \begin{cases} \|u_Z\|^2\Phi_P(\bar u_Z), & u_Z\neq 0,\\ 0, & u_Z=0. \end{cases}\] To penalize environment-dependent spurious components, define the environment-wise association statistic \[\theta_V^{(e)}:=\mathrm{Cov}_e(Y,u_V^\top X)\] and \[T(V):=\max_{e\neq e'}\big(\theta_V^{(e)}-\theta_V^{(e')}\big)^2.\] The covariance statistic is used only to detect the environment-dependent spurious block in the wrapper; the predictive hardness is inherited from the black-box primitive through \(\Phi_P\). We combine the two terms into \[S(V):=A(V)-\lambda T(V),\] where \(\lambda>0\) is chosen large enough that non-invariant spurious directions are penalized more than any gain in predictivity. In Construction 5, many directions can be invariant but non-predictive; the score \(S(V)\) combines invariance with predictive power to rule out such directions.

3.3 Statistical Learnability vs.Computational Hardness↩︎

Given Lemma 2, an exponential-time search over an \(\epsilon\)-net of \(\mathrm{Gr}(1,d)\) can recover the invariant one-dimensional subspace by maximizing an empirical version of \(S(V)\). The required sample size follows from uniform concentration over the finite net and environment pairs.

The proof follows by uniform concentration over an \(\epsilon\)-net of \(\mathrm{Gr}(1,d)\) and is given in Appendix 13.8.

To obtain hardness, we show that constant-accuracy recovery of \(V_{\mathrm{inv}}\) yields constant-overlap recovery of the hidden sparse direction in the supervised sparse primitive. Any algorithm that outputs \(\hat{V}\) with \(\mathop{\mathrm{dist}}(\hat{V},V_{\mathrm{inv}})\le \delta_0\) induces a constant-accuracy recovery of the direction \(v\) in the primitive, which by Hypothesis 4(iv) yields a solver for the underlying average-case sparse-recovery problem.

The proof is by projecting the recovered one-dimensional subspace onto the primitive block and invoking the decoder in Hypothesis 4; see Appendix 13.9.

Any approximation or sampling discrepancy included in a concrete instantiation of the primitive only changes success probabilities by the corresponding total-variation amount, so the constant-success decoding implication remains valid whenever the primitive provides such a guarantee.

4 Statistical Foundations↩︎

This section characterizes when \(V_{\mathrm{inv}}\) is identifiable and how sample complexity scales. The key quantity is environment diversity (Definition 2): insufficient diversity makes recovery statistically impossible, while sufficient diversity yields well-posed recovery with sharp finite-sample transitions.

4.1 Identifiability via Diversity↩︎

By (C1), \(\mathcal{I}_{\mathrm{gap}}(V_{\mathrm{inv}})=0\). Intuitively, if \(V\) contains only invariant information, then the predictive mechanism \(Y\mid X_V\) should not change across environments; if \(V\) mixes in spurious directions, conditioning on \(X_V\) can induce environment-dependent behavior.

Proofs for this section are deferred to Appendix 13.

4.1.0.1 A structured label-induced shift regime.

In many spurious-correlation settings, environments affect how spurious features correlate with the label rather than changing the \(Y\mid X_{\mathrm{inv}}\) mechanism. We formalize this next.

4.2 Minimax Rates↩︎

We next quantify the best possible estimation error with unlimited computation. The term \(k(d-k)\) is the intrinsic degrees of freedom of a \(k\)-dimensional subspace in \(\mathbb{R}^d\), while the factor \(n|\mathcal{E}|\) reflects the effective total sample size across environments in the balanced case.

The quantity \(\mathcal{C}_{\mathrm{sp}}\) captures how many subspaces appear approximately invariant: high diversity shrinks \(\mathcal{V}_{\mathrm{conf}}(\epsilon)\) to a neighborhood of \(V_{\mathrm{inv}}\), while low diversity can create many near-invariant “confusers.”

4.2.0.1 Interpretation of the minimax theorem.

The next result is a regular local minimax statement. Its assumptions explicitly include local quadratic curvature of the invariance gap and LAN-type Gaussian regularity. Thus the theorem should not be read as deriving these regularity properties in full generality. Rather, it states that once environment diversity yields a locally well-conditioned invariant subspace problem, the optimal statistical rate is the regular parametric Grassmannian rate with dimension \(k(d-k)\) and total sample size \(n|\mathcal{E}|\). The label-induced shift model in Section 4.3 then gives one concrete setting in which the local curvature scales with diversity.

4.3 Phase Transition and Explicit \(\gamma\)-Scaling↩︎

To make the role of diversity explicit, we specialize to the label-induced shift regime (Proposition 10). In this setting, diversity controls the smallest eigenvalue of the environment-difference matrix \(\mathcal{F}\) and hence the local curvature of invariance objectives around \(V_{\mathrm{inv}}\).

4.3.0.1 Directional diversity in the phase transition.

The explicit \(1/\gamma^2\) scaling below uses Assumption 3, which links the coordinate-level diagnostic \(\gamma\) to the spectral directional diversity \(\lambda_{\min}(\mathcal{F})\). More generally, the same argument gives rates controlled by \(1/\lambda_{\min}(\mathcal{F})\); the displayed \(1/\gamma^2\) form applies when \(\lambda_{\min}(\mathcal{F})\ge c_{\mathcal{F}}\gamma^2\).

5 Tractability Conditions↩︎

The hardness result is worst-case. In many practical settings, additional structure gives efficient certificates for recovering \(V_{\mathrm{inv}}\). We summarize four sufficient regimes.

A practical diagnostic is to compute per-feature correlation ranges \[v_j=\max_e \hat{\rho}_j^{(e)}-\min_e \hat{\rho}_j^{(e)},\qquad \hat{\rho}_j^{(e)}=\mathrm{Corr}(X_j^{(e)},Y^{(e)}),\] or the representation-space proxy \(\hat{\gamma}_{\mathrm{repr}}\). Large separation between stable predictive coordinates and varying spurious coordinates suggests that simple screening, spectral methods, or group-aware objectives should be effective. Detailed algorithms and checks are given in Appendix 16.

5.1 Connection to Real Benchmarks↩︎

Our tractability conditions provide a compact interpretation of prior benchmark behavior: datasets with low-dimensional, strongly shifting spurious signals (e.g., ColoredMNIST/CelebA/Waterbirds) approximately satisfy (T3) and favor moment- or group-aware methods, whereas high-dimensional and subtle shifts (e.g., DomainBed-style) can weaken (T2)–(T4). More discussion is in Appendix 15.

6 Experiments↩︎

We empirically study three aspects of our framework: (i) compute–sample gaps on synthetic hard instances; (ii) phase transitions and diversity-dependent thresholds; (iii) behavior on standard spurious-correlation benchmarks. Details and ablations are in Appendix 15.

6.1 Experimental Settings↩︎

6.1.0.1 Synthetic data.

We make axis-aligned instances inspired by the hardness mechanisms in Section 3, where invariant coordinates are hidden among spurious “confusers” whose cross-environment statistics partially mimic invariance. We report feature selection accuracy (fraction of true invariant coordinates among the selected top-\(k\)). We compare exhaustive subset search (exponential time) against polynomial-time baselines including invariance screening (Section 5) and other efficient heuristics (Appendix 15). Unless stated otherwise we use \(d=20\), \(k=4\), \(|\mathcal{E}|=4\) and vary \(n\) or \(\gamma\). These instances are not intended to implement the planted-clique reduction; rather, they probe compute–sample tradeoffs in regimes that create many near-invariant alternatives.

6.1.0.2 Real datasets.

We evaluate on ColoredMNIST, CelebA (Blond_Hair with spurious Male), and Waterbirds (bird type with spurious background). For ColoredMNIST we explicitly control diversity by varying the difference in color-label flip probabilities across training environments, which serves as a practical proxy for \(\gamma\) in Definition 2.

6.2 Gap, Phase Transition, and Diversity↩︎

6.2.0.1 (1) Computational gap.

On synthetic hard instances, Fig. 1 shows a large sample-complexity gap: exhaustive search achieves a fixed target accuracy with up to \(27\times\) fewer samples than the best polynomial-time method. Holding the dataset fixed, Fig. 2 further shows a monotone compute–accuracy frontier: moving from simple filtering (\(O(d)\)) to greedy (\(O(kd)\)), to beam search, and finally to exhaustive evaluation consistently improves recovery.

On real data, Table 1 exhibits an analogous small-sample separation between an oracle invariant pipeline (grayscale) and learned invariance-promoting methods: at \(N=500\) IRM trails the oracle by 10 points, while the gap shrinks at \(N=2000\), consistent with increased data easing the learning problem. Since the oracle uses grayscale preprocessing (different input), this gap should be interpreted cautiously: it suggests the difficulty of discovering invariant structure from finite multi-environment data rather than proving computational hardness for deep networks. Adv-Color partially controls for input differences by using the same colored input while explicitly suppressing color information.

6.2.0.2 (2) Phase transitions.

Fig. 2 shows phase-transition behavior: on synthetic instances, polynomial-time methods transition sharply from failure to success around a critical sample size, while exhaustive search stays near-optimal across the range. On ColoredMNIST, the same figure shows a smoother but qualitatively similar improvement with \(n\), and Table 1 confirms that the small-sample regime is where invariant learning is most brittle and additional samples quickly reduce the gap. Additional training dynamics are deferred to Appendix (Fig. 3).

2.5pt

CMNIST: Low=\(\gamma=0\), High=\(\gamma=0.8\)

. CelebA/Wbirds use bias strength as an operational proxy: Low=shared spurious bias 0.9, High=reduced shared bias 0.0.

6.2.0.3 (3) Diversity is necessary.

Fig. 2 visualizes diversity necessity: on synthetic data, performance is poor when \(\gamma=0\) and increases sharply once environments become informative; on ColoredMNIST, both OOD and worst-group accuracy improve as diversity increases. Table 2 extends this pattern across datasets: moving from the operational low-diversity/high-bias setting to the operational high-diversity/low-bias setting improves worst-group accuracy on CelebA and Waterbirds and improves OOD accuracy on ColoredMNIST. Finally, Table 3 shows that a representation-space proxy \(\hat{\gamma}_{\mathrm{repr}}\) computed on ERM features correlates with worst-group performance, supporting diversity estimates as a practical diagnostic.

6.3 Tractability Validation on Synthetic Data↩︎

Table 4 connects Section 5 to empirical performance by varying structural factor at a time. Increasing diversity (\(\gamma=0.1\to 0.6\)) yields the largest gain, consistent with the identifiability/curvature role of \(\gamma\) (Section 4). Increasing sample size (\(n=200\to 2000\)) improves performance but with diminishing returns once diversity is high, matching phase-transition intuition. Reducing \(k\) (a proxy for sparsity / effective search-space size) improves recovery, aligning with (T1). Increasing SNR helps but does not replace diversity, illustrating noise and diversity are distinct bottlenecks.

6.4 Practical Guidance and Diagnostics↩︎

Compute a diversity proxy \(\hat{\gamma}_{\mathrm{repr}}\) in representation space (Table 3) by applying Definition 3 to learned features. If it is small, collecting more diverse environments is typically more effective than collecting more samples from similar environments. When performance improves monotonically with compute at fixed data (Fig. 2), the instance behaves like a hard regime where efficient objectives may struggle.

6.4.0.1 Related Work.

We build on spurious-correlation and invariant learning benchmarks (e.g., IRM/REx and GroupDRO) and on average-case computational lower bounds for sparse recovery, including Planted-Clique-motivated samplable reductions. A detailed discussion and references are deferred to Appendix 10.

7 Conclusion↩︎

We establish a conditional computational–statistical gap for spurious correlation removal: under a black-box samplable supervised sparse recovery primitive, there exist samplable multi-environment instances where the predictive invariant subspace is identifiable as the unique maximizer of an invariance–predictivity population score and learnable with polynomial samples by exhaustive search, yet any polynomial-time constant-accuracy recovery algorithm at comparable sample sizes would contradict the primitive. We also characterize the role of environment diversity in identifiability and finite-sample behavior, obtaining minimax risk \(\Theta(k(d-k)/(n|\mathcal{E}|))\) under sufficient diversity and local Gaussian regularity, and a label-induced phase transition at \(n^*\propto k(d-k)/(|\mathcal{E}|\gamma^2)\) with refined estimation error scaling proportional to \(1/\gamma^2\). Finally, we give tractability conditions under which efficient methods achieve near-optimal rates. Future work includes sharper gap frameworks and extending lower bounds beyond linear-Gaussian models.

Acknowledgements↩︎

This work was partially supported by the “Pioneer” and “Leading Goose” R&D Program of Zhejiang (Grant No.2025C01037) and the Key R&D Program Project of Hangzhou (Grant No.2024SZD1A03).

Impact Statement↩︎

7.0.0.1 Positive.

Our framework helps practitioners diagnose failures in invariant learning by distinguishing statistical limitations (insufficient samples or diversity) from potential computational barriers (hard problem structure). This can:

• reduce wasted effort on algorithmic improvements when the issue is data diversity;

• guide data collection toward more informative environments rather than simply more samples;

• improve deployment decisions by identifying when learned models may be unreliable under shift.

7.0.0.2 Potential negative impacts.

Conditional worst-case hardness results could be misinterpreted as discouraging work on invariant learning or as evidence that such methods are fundamentally flawed. We emphasize:

• many practical problems satisfy tractability conditions (Section 5), explaining why invariant learning often works;

• our hardness results are worst-case conditional constructions, not claims about typical problems.

8 Overview of Appendix↩︎

This appendix provides formal proofs, proof refinements, implementation details, extended experiments, and practical guidance supporting the main text.

It is organized as follows:

• Appendix 9: notation summary.

• Appendix 10: additional related work and positioning.

• Appendix 11: formal restatements and logical status of the main theoretical claims.

• Appendix 12: status of the supervised sparse primitive and scalar covariance sanity checks.

• Appendix 13: complete proofs and proof refinements.

• Appendix 14: connection to Planted-Clique-based sparse CCA reductions.

• Appendix 15: experimental details and extended results.

• Appendix 16: practical diagnostic guide.

8.0.0.1 Important logical clarification.

The computational lower bound uses the supervised sparse recovery primitive in Hypothesis 4 as a black-box average-case hardness primitive. Existing Planted-Clique-to-sparse-CCA reductions motivate this type of sparse-recovery hardness, but sparse CCA is naturally a two-view/vector-response problem. We therefore do not claim that the supervised scalar-response primitive follows directly from existing sparse CCA reductions. In particular, the primitive should not be interpreted as the exposed scalar covariance model \(\mathrm{Cov}(Z,Y)=\lambda v\), which can be easy by empirical covariance estimation in some regimes.

9 Notation Summary↩︎

Table 5 summarizes the main symbols used in the paper and appendix. We separate statistical quantities such as \(\gamma\), \(\mathcal{I}_{\mathrm{gap}}\), and \(\mathcal{C}_{\mathrm{sp}}\) from computational-hardness quantities such as \(d_Z\), \(s\), \(v\), and \(\Phi_P\), reflecting the two components of our framework.

10 Additional Related Work and Positioning↩︎

This section expands the literature context and clarifies how our results differ from existing work on invariant learning, identifiability, and computational lower bounds.

10.1 Invariant learning and identifiability↩︎

IRM, REx, GroupDRO, and related methods aim to learn predictors whose label mechanism is stable across environments. Prior theory emphasizes that multi-environment information is useful only when environments are sufficiently diverse; otherwise, invariances can be statistically unidentifiable. Our work is complementary: even when invariant structure is identifiable in a population sense, efficient recovery can still be obstructed under a conditional sparse-recovery hardness primitive.

10.2 Computational-statistical gaps↩︎

Average-case reductions from Planted Clique are a standard tool for demonstrating computational-statistical gaps in high-dimensional statistics, especially sparse PCA and sparse CCA. Our reduction differs in that the target problem is multi-environment invariant subspace recovery. The embedding must preserve the invariance condition and must be samplable without using the hidden sparse direction or its support.

10.3 Relation to sparse CCA and scalar supervised primitives↩︎

Sparse CCA reductions naturally produce vector-response two-view models. The supervised scalar-response sparse primitive used in the main text is treated as a black-box primitive rather than as a direct consequence of sparse CCA. Appendix 14 explains the relationship and the limitation of directly projecting sparse CCA to a scalar response.

11 Formal Restatements and Logical Status↩︎

12 Logical Status of the Supervised Sparse Primitive↩︎

12.1 A covariance-estimator sanity check↩︎

13 Complete Proofs↩︎

13.1 Proof of Proposition 24 (Proxy Approximation)↩︎

13.2 Proof of Theorem 9↩︎

13.3 Proof of Proposition 10 and Corollary 1↩︎

13.3.0.1 Gaussian conditional parameters.

Let \[A=X_{\mathrm{inv}},\qquad B^{(e)}=X_{\mathrm{sp}}^{(e)},\qquad p=d-k.\] In the label-induced model, \[Y=w^{*\top}A+\epsilon,\qquad B^{(e)}=\mu_{\mathrm{sp}}^{(e)}Y+\eta^{(e)}.\] For a candidate subspace \(V\) with orthonormal basis \[Q= \begin{pmatrix} Q_A\\Q_B \end{pmatrix},\] define \[T_e=Q^\top X^{(e)},\qquad r_e=Q_B^\top\mu_{\mathrm{sp}}^{(e)}.\] Then \[T_e=(Q_A^\top+r_ew^{*\top})A+r_e\epsilon+Q_B^\top\eta^{(e)}.\] The conditional law \(Y\mid T_e\) is Gaussian with parameters \[\beta_e=\Sigma_{T,e}^{-1}c_e,\qquad \sigma_{e|T}^2=\sigma_Y^2-c_e^\top\Sigma_{T,e}^{-1}c_e,\] where \[c_e=Q_A^\top w^*+\sigma_Y^2r_e\] and \[\Sigma_{T,e} = I_k+Q_A^\top w^*r_e^\top+r_ew^{*\top}Q_A+\sigma_Y^2r_er_e^\top.\]

13.4 Proof of Theorem 14 and Corollary 2↩︎

13.4.0.1 Local chart.

Near \(V_{\mathrm{inv}}\), write \[Q_\Theta= \begin{pmatrix} I_k\\\Theta \end{pmatrix} (I_k+\Theta^\top\Theta)^{-1/2}, \qquad \Theta\in\mathbb{R}^{(d-k)\times k}.\] For small \(\Theta,\Theta'\), \[\mathop{\mathrm{dist}}(V_\Theta,V_{\Theta'}) \asymp \|\Theta-\Theta'\|_F.\] The local dimension is \(q=k(d-k)\).

13.4.0.2 Lower bound.

Take a local packing of size \(\log M\gtrsim q\) with pairwise distance \(\epsilon\). Gaussian KL regularity gives \[\mathrm{KL}(P_{\Theta_i}^{\otimes N}\|P_{\Theta_j}^{\otimes N}) \le CN\epsilon^2.\] Choosing \(\epsilon^2\asymp q/N\) and applying Fano yields \[\inf_{\hat{V}}\sup_{\mathbb{P}} \mathbb{E}[\mathop{\mathrm{dist}}(\hat{V},V_{\mathrm{inv}})^2] \gtrsim \frac{q}{N}.\]

13.4.0.3 Upper bound via LAN.

Under local Gaussian LAN regularity, the local MLE satisfies \[\hat{\Theta}-\Theta_0 = I(\Theta_0)^{-1}\frac{1}{N}\nabla_\Theta L_N(\Theta_0) +o_{\mathbb{P}}(N^{-1/2}),\] where \[cI_q\preceq I(\Theta_0)\preceq CI_q.\] Therefore \[\mathbb{E}\|\hat{\Theta}-\Theta_0\|_F^2 \le C\frac{q}{N}.\] Using the local chart equivalence gives \[\mathbb{E}[\mathop{\mathrm{dist}}(\hat{V},V_{\mathrm{inv}})^2] \le C\frac{k(d-k)}{n|\mathcal{E}|}.\] The entropy term \(\mathcal{C}_{\mathrm{sp}}\) enters when model selection among approximately invariant local basins is required.

13.5 Proof of Theorem 16↩︎

13.6 Samplable Sparse-Recovery Primitive and Embedding Details↩︎

This section clarifies how Hypothesis 19 is embedded into the SC instance.

13.6.0.1 Samplability.

Given \(A\), Construction 5 runs \(\mathcal{R}(A)\) independently in each environment and then samples \[W^{(e,t)}=\mu^{(e)}Y^{(e,t)}+\eta^{(e,t)}\] using public randomness. The hidden sparse direction and its support are never used.

13.6.0.2 SC validity.

Construction 5 satisfies the SC conditions as in Lemma 1: by Hypothesis 4, \(Y\mid X_{\mathrm{inv}}\) depends only on \(v^\top Z\) and is identical across environments, while \(W\mid X_{\mathrm{inv}}\) varies with \(\mu^{(e)}\). The sampler-generated construction inherits the recovery and hardness statements up to the total-variation discrepancies specified by the primitive, when applicable.

13.7 Proof of Lemma 2↩︎

Let \(u=(u_Z,a)\) be a unit vector spanning \(V\), where \(u_Z\in\mathbb{R}^{d_Z}\) and \(a\in\mathbb{R}\). Let \(u^*=(v,0)\) span \(V_{\mathrm{inv}}\), and write \(r=\|u_Z\|=(1-a^2)^{1/2}\). If \(r>0\), define \(\bar u_Z=u_Z/r\).

For the true direction, \[S(V_{\mathrm{inv}})=A(V_{\mathrm{inv}})=\Phi_P(v), \qquad T(V_{\mathrm{inv}})=0.\] Since \(0\le \Phi_P\le 1\) and the primitive margin is positive, \(\Phi_P(v)\) is bounded below by a positive constant depending on \(c_{\mathrm{prim}}\).

We first compute the invariance penalty. In Construction 5, \[u^\top X=u_Z^\top Z+aW^{(e)} =u_Z^\top Z+a\mu^{(e)}Y+a\eta^{(e)} .\] The primitive samples \((Z,Y)\) have the same distribution in every environment, and \(\eta^{(e)}\) is independent of \(Y\). Hence \[\theta_V^{(e)} =\mathrm{Cov}_e(Y,u^\top X) =\mathrm{Cov}(Y,u_Z^\top Z) +a\mu^{(e)}\mathrm{Var}(Y).\] Therefore, for any pair \(e,e'\), \[\theta_V^{(e)}-\theta_V^{(e')} = a(\mu^{(e)}-\mu^{(e')})\sigma_Y^2,\] and consequently \[T(V) = \max_{e,e'}(\theta_V^{(e)}-\theta_V^{(e')})^2 = a^2\Delta_\mu^2\sigma_Y^4 .\]

Fix the target separation radius \(\delta\in(0,1)\). Choose a small constant \(\alpha=\alpha(\delta)>0\). We split into two cases.

13.7.0.1 Case 1: \(|a|\ge \alpha\).

Since \(A(V)\le 1\), \[S(V)\le 1-\lambda\alpha^2\Delta_\mu^2\sigma_Y^4 .\] Choosing \(\lambda\) sufficiently large, depending only on \(\alpha,\Delta_\mu,\sigma_Y^2\), ensures \[S(V)\le S(V_{\mathrm{inv}})-c_1\] for some constant \(c_1>0\).

13.7.0.2 Case 2: \(|a|<\alpha\).

For \(\alpha\) sufficiently small as a function of \(\delta\), the condition \(\mathop{\mathrm{dist}}(V,V_{\mathrm{inv}})\ge\delta\) implies that \(\mathrm{span}(\bar u_Z)\) is bounded away from \(\mathrm{span}(v)\) by a constant \(\delta'=\delta'(\delta)>0\). By the primitive margin, \[\Phi_P(\bar u_Z)\le \Phi_P(v)-c_{\mathrm{prim}}'\] for some \(c_{\mathrm{prim}}'>0\) depending only on \(c_{\mathrm{prim}}\) and \(\delta'\). Since \(r^2\le 1\) and \(T(V)\ge0\), \[S(V) = r^2\Phi_P(\bar u_Z)-\lambda T(V) \le \Phi_P(v)-c_{\mathrm{prim}}' = S(V_{\mathrm{inv}})-c_{\mathrm{prim}}' .\] If \(r=0\), then \(A(V)=0\) by definition and the same conclusion is immediate.

13.8 Proof of Lemma 3↩︎

Take an \(\epsilon\)-net of \(\mathrm{Gr}(1,d)\) of size at most \((C/\epsilon)^{d-1}\). The primitive concentration assumption gives uniform convergence of the empirical predictive score, and the bounded-moment condition gives uniform concentration of the wrapper covariance statistics over the net. With \[n_{\min} \gtrsim \frac{d\log(C/\epsilon)+\log(|\mathcal{E}|/\delta)}{c_{\mathrm{mar}}^2},\] up to primitive-dependent polynomial factors, the empirical score is uniformly within \(c_{\mathrm{mar}}/4\) of the population score. The margin in Lemma 2 then implies that the empirical maximizer lies within constant distance of \(V_{\mathrm{inv}}\).

13.9 Proof of Lemma 4↩︎

For one-dimensional subspaces, \[\|P_{\hat{V}}-P_{V_{\mathrm{inv}}}\|_F^2=2\sin^2\phi,\] where \(\phi\) is the principal angle. Hence \[|\langle \hat{u},(v,0)\rangle|^2\ge1-\delta_0^2/2.\] Restricting \(\hat{u}\) to the \(Z\)-block gives constant overlap with \(v\), sufficient for the primitive decoder in Hypothesis 19. Therefore any polynomial-time SC recovery algorithm would solve the underlying average-case sparse-recovery problem, contradicting the hardness clause in Hypothesis 4.

13.10 Proof of Theorem 18↩︎

Theorem 18 is a summary of sufficient tractability templates. Representative formal versions are given below.

14 Connection to PC-Based Sparse CCA Reductions↩︎

This section is motivational and does not serve as a formal derivation of Hypothesis 19. The formal hardness assumption used in the paper is the black-box supervised sparse recovery primitive in Hypothesis 4.

Sparse CCA observes two Gaussian views \((Z,U)\) with \[\operatorname{Cov}(Z,U)=\lambda vw^\top,\] where \(v,w\) are sparse. Standard Planted-Clique-based reductions establish hardness of sparse CCA in certain regimes.

A scalar-response supervised primitive may be heuristically related to sparse CCA by projecting \(U\) to a scalar \(Y=g^\top U\), which gives \[\operatorname{Cov}(Z,Y)=\lambda(g^\top w)v.\] However, this projection changes the signal strength and may enter regimes where simple covariance estimation succeeds. Therefore Hypothesis 19 is used as a black-box conditional sparse predictive recovery assumption rather than derived directly from sparse CCA.

15 Experimental Details↩︎

This section preserves the experimental details and labels referenced in the main text.

15.1 Synthetic Data Generation↩︎

We generate synthetic data using the linear Gaussian construction described in the main text. The invariant features satisfy \[X_{\mathrm{inv}}\sim\mathcal{N}(0,I_k), \qquad Y=\langle \mathbf{1}_k/\sqrt{k},X_{\mathrm{inv}}\rangle+\epsilon.\] Spurious features are generated with environment-dependent correlations with \(Y\). The diversity parameter is controlled through the range of these correlations.

Algorithms include exhaustive subset search, invariance screening, greedy forward selection, beam search, and spectral baselines.

15.2 Extended Results↩︎

This subsection provides additional empirical results supporting the main-text claims. Table 6 reports extra ColoredMNIST results across diversity levels, Table 7 summarizes worst-group accuracy as sample size increases, and Table 8 together with Fig. 3 shows the training dynamics of IRM on ColoredMNIST.

Table 6 complements the main ColoredMNIST results by varying both diversity and sample size. When \(\gamma=0\), worst-group accuracy remains low, indicating that additional samples alone cannot fully resolve the lack of informative environment variation. As \(\gamma\) increases, both ERM and IRM improve, with IRM benefiting more in worst-group accuracy, consistent with the role of environment diversity in identifying invariant structure.

Table 7 illustrates the sample-size effect on real benchmarks. Worst-group accuracy generally improves as \(N\) increases, supporting the finite-sample transition picture in the main text. The gains are especially visible in the small-to-moderate sample regime, suggesting that invariant or group-aware methods are most brittle when both diversity and sample size are limited.

Table 8 shows that OOD and worst-group accuracy improve throughout IRM training, while \(\hat{\gamma}_{\mathrm{repr}}\) computed on the evolving IRM representation decreases. This is not in conflict with the diversity diagnostic in the main text: there, \(\hat{\gamma}_{\mathrm{repr}}\) is used on preliminary ERM features to assess whether environments expose spurious variation, whereas during IRM training a decreasing proxy can indicate that color-related spurious information is being suppressed in the learned representation.

Fig. 3 visualizes the same training behavior. OOD accuracy rises quickly, while worst-group accuracy improves more slowly and saturates later. This gap between average OOD performance and worst-group robustness is consistent with the main-text observation that invariant structure may be statistically useful before it is fully recovered by practical training objectives.

16 Practical Application Guide↩︎

Fig. 4 summarizes the practical workflow suggested by our theory and experiments. The key diagnostic is to first estimate representation-level diversity; if diversity is low, collecting more diverse environments is prioritized, whereas if diversity is adequate but the sample size is below the predicted threshold, collecting more samples or reducing effective dimension is recommended.

The flowchart in Fig. 4 is intended as a heuristic decision aid rather than a formal algorithm. It operationalizes the two main quantities emphasized in the paper: diversity, estimated by \(\hat{\gamma}_{\mathrm{repr}}\), and effective sample complexity, estimated through the scaling \(n^*\propto k_{\mathrm{eff}}(d_{\mathrm{eff}}-k_{\mathrm{eff}})/(|\mathcal{E}|\hat{\gamma}_{\mathrm{repr}}^2)\). In practice, these estimates should be combined with validation performance and worst-group metrics when available.

16.0.0.1 Step-by-step guide.

1. Train a preliminary ERM model and compute \(\hat{\gamma}_{\mathrm{repr}}\) on penultimate features.

2. If \(\hat{\gamma}_{\mathrm{repr}}\) is small, prioritize collecting more diverse environments.

3. Estimate the critical scaling \[n^*\propto \frac{k_{\mathrm{eff}}(d_{\mathrm{eff}}-k_{\mathrm{eff}})}{|\mathcal{E}|\hat{\gamma}_{\mathrm{repr}}^2}.\]

4. If \(n\ll n^*\), collect more samples or reduce effective dimension.

5. Choose methods based on structure: GroupDRO when groups are available, IRM/REx when environments are informative, and spectral or screening methods when tractability conditions hold.

16.0.0.2 Limitations.

The statistical theory is linear-Gaussian, and the computational component is worst-case and conditional on the black-box supervised sparse recovery primitive. The hardness result should be interpreted as a conditional lower bound for constructed hard families, not as a claim about typical benchmark datasets.

References↩︎