Computational Double Robustness: When Is a Causal Effect Hard to Estimate Efficiently?

Adjusting for confounders means removing the part of a treatment–outcome association that comes from variables affecting both. When there are many candidate confounders and they act through nonlinear functions, estimating how treatment is assigned (the propensity) and how the outcome depends on covariates can each become computationally hard. In those regimes a brute-force search would succeed with about $d$ samples in $d$ dimensions, while every fast algorithm needs polynomially more. This proposal asks whether that hardness carries over to the single number practitioners care about, the average treatment effect. We conjecture a precise answer: the efficient sample cost of the effect is set by whichever of the two nuisance problems (propensity or outcome model) is easier. We call this computational double robustness. We propose to prove matching lower and upper bounds in a Gaussian single-index confounding model and to test whether flexible learners and causal foundation models respect the predicted threshold.

The question is open for a concrete reason. Estimating a scalar functional can sometimes be much easier than recovering the high-dimensional parameters behind it, so hardness results for recovery do not settle hardness of effect estimation. If the conjecture holds, it tells applied researchers exactly when "adjust for everything with a flexible model" has a sample-size cost no clever algorithm can avoid. If it fails, there is a cheap estimator that bypasses both nuisance problems, and that would be even more useful.

Core Claim

Take Gaussian covariates $X \sim N(0, I_d)$. Treatment is binary, with $P(T=1 \mid X) = p(\langle w, X\rangle)$. The outcome is $Y = \tau T + f(\langle v, X\rangle) + \text{noise}$, where $w$ and $v$ are unknown unit directions with overlap $\rho = \langle v, w\rangle \neq 0$ (the source of confounding), and $\tau$ is the effect to estimate.

Each nuisance link has a generative exponent, $k_T$ for $p$ and $k_Y$ for $f$. Following Computational-Statistical Gaps in Gaussian Single-Index Models, this is the index of the first Hermite polynomial that the link (after the best transformation of the label) correlates with. That paper shows recovering such a direction needs about $d$ samples information-theoretically but $\Omega(d^{k^*/2})$ for statistical-query and low-degree algorithms, and that a partial-trace tensor method achieves this rate.

Our claim is that for estimating $\tau$ to constant accuracy,

$$ n_{\text{poly}}(\tau) \asymp d^{\,\max(1,\ \min(k_T, k_Y)/2)}, \qquad n_{\text{info}}(\tau) \asymp d . $$

Here $n_{\text{poly}}$ is the sample size needed by low-degree or statistical-query estimators and $n_{\text{info}}$ is the brute-force requirement.

The upper bound comes from a doubly robust estimator, which combines a propensity model and an outcome model and stays consistent if either one is accurate. We plug in the partial-trace learner for whichever nuisance has the smaller exponent. The lower-bound intuition is a Hermite expansion of the naive bias:

$$ \mathbb{E}[Y \mid T=1] - \mathbb{E}[Y \mid T=0] - \tau = \frac{1}{\pi(1-\pi)} \sum_{j} c^f_j\, c^T_j\, \rho^{j}. $$

Here $\pi = P(T=1)$, and $c^f_j$ and $c^T_j$ are the $j$-th Hermite coefficients of the two links. The bias lives only at degrees $j \ge \max(k_T, k_Y)$. Removing it therefore requires, at minimum, statistics of degree at least $\min(k_T, k_Y)$ that are correlated with the confounding direction. Low-degree hardness then says these statistics are uninformative below $d^{\min(k_T,k_Y)/2}$ samples.

The part we do not yet know, and which the theory must settle, is whether a "cross-moment" estimator can remove the bias without learning either direction. Such an estimator would estimate the overlap of the degree-$j$ tensors $\mathbb{E}[T\,H_j(X)]$ and $\mathbb{E}[Y\,H_j(X)]$ with a U-statistic. Our heuristic variance calculation says it costs $d^{j/2}$ at degree $j \ge \max(k_T,k_Y)$, so it cannot beat the doubly robust route, but this has to be proved.

Relation to Prior Work

Two papers motivate the claim by showing gaps in adjacent problems.

Lasso with Latents proves a $k$ versus $k^2$ low-degree gap for sparse regression when hidden factors distort the covariate covariance. It studies prediction, not the effect of a designated treatment, and it has no treatment–outcome confounding.

Confounder Detection in High-Dimensional Linear Models Using First Moments of Spectral Measures tests for hidden confounding using spectral moments. Its analysis is asymptotic and linear, and it gives no efficient-versus-brute-force sample threshold. We study nonlinear, observed but high-dimensional confounding, and we ask for thresholds rather than tests.

Two papers supply the method. The single-index paper above provides the hardness machinery and the partial-trace algorithm. We reuse both, shifting the target from recovering a direction to estimating a functional that depends on two interacting directions. Its restriction to Gaussian designs constrains our scope equally, and we state this upfront.

A third group constrains the empirical side. Causal Foundation Models Perform Better without Post-treatment Variables shows that CausalPFN and Do-PFN behave as S-learners, meaning they fit one outcome model on all inputs and toggle the treatment. That observation predicts they inherit the outcome exponent $k_Y$ rather than the minimum of the two exponents, which is a sharp, falsifiable prediction for our experiments. Do-PFN and CausalPFN claim broad graph-agnostic effect estimation. Neither studies how error scales with dimension, which is exactly where computational barriers would show.

Research Program

The theoretical work has three pieces.

The first is an upper bound. We will prove that a cross-fitted doubly robust estimator, using partial-trace nuisance estimates, attains constant error at $n \asymp d^{\min(k_T,k_Y)/2}$ up to logarithmic factors. The key step is showing that a poor estimate of the harder nuisance is harmless when the easier one is accurate.

The second is a lower bound. We will build a low-degree indistinguishability argument between two planted instances with different $\tau$ but matched low-degree moments. A natural construction pairs $(\tau, \rho)$ against $(\tau', \rho')$ so that all joint moments of degree below $\min(k_T,k_Y)$ agree.

The third is a sparse extension. We will ask whether, when the confounding directions are $k$-sparse, the gap reduces to the $k$ versus $k^2$ form seen in Lasso with Latents and Computationally Efficient Robust Sparse Estimation in High Dimensions.

If the lower bound fails because the cross-moment estimator beats the minimum, we will report that estimator and its rate instead. Either outcome is a result.

Baselines

The naive reference is the difference in outcome means between treated and untreated units. Its bias is known in closed form from the Hermite formula above. It sets the ceiling of how wrong one can be, and every method should beat it once $n$ exceeds its own threshold.

The standard applied baseline is multivariable linear regression of $Y$ on $T$ and all of $X$, the workhorse in the adjustment literature. It removes only degree-one confounding, so it should remain biased whenever $\min(k_T,k_Y) \ge 2$. We run it with the same samples as every other method.

The strongest practical competitors are flexible learners, which a reviewer would expect to handle nonlinearity. We use a neural doubly robust estimator trained by gradient descent, and a causal forest, which Really Doing Great at Estimating CATE? shows can outperform neural methods on additive-effect data. Both get the same data, cross-fitting splits, and a fixed hyperparameter search budget matched to our method's wall-clock time. We also run CausalPFN and Do-PFN zero-shot using the Do-PFN codebase, restricted to dimensions that fit their context windows.

No reported result was found on Lacuna for any of these methods on single-index confounding with controlled generative exponents. The nearest reported figures are on IHDP: mean absolute ATE error 0.62 for UTVAE versus 1.03 for CEVAE (Causal Effect Variational Autoencoder with Uniform Treatment). CausalPFN has the best average PEHE rank there, with no numeric value found on Lacuna (CausalPFN). We treat IHDP only as a sanity check. The critique paper shows its data-generating process favors particular estimator families, and the known IHDP settings are low-exponent.

The ablation that isolates the key ingredient keeps the partial-trace nuisance learner but uses it inside a plug-in estimator that relies on one nuisance only, first the propensity and then the outcome. If computational double robustness is real, each plug-in version should track its own exponent. The doubly robust version should track the minimum.

The information-theoretic reference is a brute-force estimator that searches over directions on a grid, feasible for $d \le 12$. It shows the $O(d)$ curve the efficient methods cannot reach.

"Beating" a baseline means one of two things. Either our method reaches a fixed ATE error at a sample size scaling with a strictly smaller exponent of $d$, or the baseline's error plateaus at the confounding bias while ours does not.

Why not just…?

Why not just adjust for all covariates in a multivariable regression? The Hermite bias formula shows linear adjustment removes only the $j=1$ term. When both links have exponent at least 2, all remaining confounding survives, however large $n$ is. The first experiment grid will show this as a flat error curve at the predicted bias.

Why not just use a flexible machine-learning doubly robust estimator; isn't this folklore? This is the real threat. The upper-bound half of our claim is close to known doubly robust reasoning. Two things are new. The first is the lower bound, meaning no efficient procedure, including ones that never estimate a nuisance, does better. The second is the observation that gradient-trained nuisance models can be slower than the $d^{k/2}$ rate, since gradient methods sit inside the statistical-query class. If the neural doubly robust estimator matches partial-trace scaling empirically, we will say so. The contribution then narrows to the lower bound, and to showing that practitioners already sit at the efficient frontier.

Why not just expand the covariates into polynomial features up to degree $k$ and run ridge regression? That introduces about $d^k$ features and needs roughly $d^k$ samples. That is quadratically worse than $d^{k/2}$, and our scaling experiments will measure the difference directly.

Why not just use a causal foundation model? The S-learner analysis in Causal Foundation Models Perform Better without Post-treatment Variables predicts these models inherit $k_Y$ and ignore an easy propensity. We test this by holding $k_Y$ high and making $k_T$ small. A foundation model that succeeds there would contradict the S-learner account, which would be interesting in itself.

Proposed Experiments

The main benchmark is a synthetic family covering $(k_T, k_Y) \in \{1,2,3,4\}^2$, with $d$ from 8 to 256, overlap $\rho \in \{0.3, 0.7\}$, and $n$ on a log grid. For each method we record the smallest $n$ at which absolute ATE error falls below $0.1\,|\text{bias}_{\text{naive}}|$, and fit the exponent of $d$. We report median error with interquartile ranges rather than means, following the long-tail warning in Really Doing Great at Estimating CATE?.

The decisive check is the off-diagonal cells, $(k_T, k_Y) = (2,4)$ and $(4,2)$. There the conjecture predicts that the doubly robust estimator's fitted exponent is about 1 in both cells. The propensity-only plug-in should be about 1 in the first cell and about 2 in the second, and the outcome-only plug-in the reverse. Foundation models should follow the outcome-only pattern.

The second check targets the diagonal cell $(4,4)$. There we test whether the cross-moment U-statistic beats $d^2$, which would falsify the lower-bound conjecture.

Finally, we move beyond Gaussian designs by pushing semi-synthetic IHDP and ACIC 2016 covariates through the same single-index treatment and outcome links. This checks whether the thresholds survive realistic, non-Gaussian covariates, which the original theory does not cover.