betaFeedback

WorksMathematics

Convex Mixed-Integer Programming for Invariant Predictions from Multi-environment Data

Abstract

Heterogeneous data provide an opportunity to identify causal predictors by revealing which predictive relationships remain invariant. Under a linear model, we introduce a least-squares coefficient-and-risk (LSCR) invariance principle, requiring both ordinary least squares coefficients and prediction risks to remain constant across environments. Our model neither specifies an intervention mechanism nor assumes a structural causal model for the entire system. We develop an invariance score that quantifies departures from LSCR invariance and use its optimization to construct two complementary procedures for causal predictor identification. First, we propose an estimator that jointly minimizes prediction risk and invariance penalty, and establish non-asymptotic guarantees for estimation and recovery of the causal parents under suitable identifiability conditions. Second, without requiring full identifiability, we develop a testing procedure that minimizes the invariance score over all predictor sets excluding a given variable, enabling valid causal discoveries with asymptotic error control via a multiplier bootstrap. Both procedures admit convex mixed-integer optimization formulations that avoid exhaustive subset enumeration while providing certificates of optimality. Simulations and real data experiments demonstrate substantial statistical and computational improvements over existing methods.

Introduction

Identifying the causal predictors of a target response is an important problem in causal inference. However, data from a single observational distribution generally cannot distinguish causal predictors from noncausal variables that are associated with the response. Data collected across varying settings and conditions, broadly called environments, offer an additional source of information for causal discovery. Although interventions or distributional changes may alter the distributions of covariates and their associations with the response, the causal mechanism governing the response remains invariant across environments, provided it is not directly intervened upon.

This idea underlies the invariant causal prediction framework of Peters et al. [18]. Let S⋆S^{\star} denote the causal parent set of a target response YY. If the causal mechanism for YY is unchanged, then the conditional distribution of YY given XS⋆X_{S^{\star}} remains invariant across environments. This establishes a connection between invariance and causality: the true causal parent set must yield an invariant conditional distribution, and any predictor set exhibiting such invariance is a natural candidate for the causal parent set. Motivated by this connection, Peters et al. [18] identify invariant predictor sets across environments and take their intersection to recover a subset of S⋆S^{\star}.

Since the work by Peters et al. [18], exploiting invariance across environments has become an important strategy for causal discovery. One line of research estimates invariant predictive models through optimization, typically by incorporating a tractable property of invariance into the estimation objective. Under suitable identifiability conditions, these methods can recover the true causal model. Arjovsky et al. [1] provide an early example with invariant risk minimization (IRM), which seeks a data representation such that the same prediction rule minimizes the risk in every environment. However, IRM does not generally guarantee recovery of the causal parent set, even in linear settings, and its practical implementation relies on highly heuristic nonconvex optimization that can be sensitive to initialization and tuning parameters [11, 20].

Other approaches focus on estimating causal regression coefficients. Rothenhäusler et al. [21] propose Causal Dantzig, which estimates causal coefficients in linear structural models using invariant moment conditions under additive interventions. More recently, Wang et al. [24] developed NegDRO, a nonconvex minimax approach that exploits invariance of prediction risks to identify causal coefficients. Although both Causal Dantzig and NegDRO can accommodate hidden confounding, they rely on specific additive intervention mechanisms and assume a linear structural causal model for the entire system, which may limit their applicability.

In contrast, EILLS, introduced by Fan et al. [5], and CoCo, proposed by Yin et al. [27], do not require a specific intervention mechanism. Both approaches exploit the first order optimality conditions of least squares regression across environments to identify causal coefficients. EILLS incorporates an invariance penalty into the regression objective, together with indicators for selected features, whereas CoCo relies on continuous nonconvex optimization. Another method is Bayesian invariant prediction (BIP), proposed by Wu et al. (2025), which uses latent binary indicators to select variables whose conditional relationship with the response remains invariant across environments.

Among these methods, only EILLS and BIP explicitly select subsets of predictors when identifying an invariant model, while sparse formulations of Causal Dantzig perform variable selection through ℓ1\ell_{1} regularization. However, the exact implementations of EILLS and BIP require exhaustive enumeration over candidate predictor subsets, making them computationally prohibitive even in moderate dimensions. Although their approximate implementations alleviate this computational burden, they lack any optimality guarantees. In contrast, ℓ1\ell_{1}-regularized Causal Dantzig admits a computationally tractable convex formulation, but its reliance on a convex relaxation of variable selection may lead to shrinkage biases and inaccurate support recovery.

The methods discussed above, including IRM, Causal Dantzig, NegDRO, EILLS, CoCo, and BIP, generally require sufficient intervention heterogeneity to guarantee recovery of the causal parent set. Without such heterogeneity, the variables discovered by these methods may include noncausal predictors, and recovery of even a subset of the true causal parent set is not guaranteed.

An alternative line of work seeks to identify a subset of the causal parent set while controlling type-I error, without requiring full identifiability. As discussed earlier, Peters et al. [18] introduce invariant causal prediction (ICP), which tests invariance over all candidate predictor subsets and takes the intersection of the accepted sets. However, exhaustive enumeration of predictor subsets becomes computationally prohibitive as the dimension increases. To address this limitation, Martinet et al. [15] formulate causal predictor discovery as a multiple testing problem instead of exhaustive subset enumeration. These tests use Wasserstein variance minimization (WVM) to assess whether the conditional distribution of the response can remain invariant across environments when a given variable is excluded. However, WVM remains computationally expensive. Moreover, both ICP and WVM can have limited statistical power in identifying causal predictors, particularly at moderate sample sizes.

Gaps and our contributions

Gaps and our contributions. The preceding discussion highlights two related but distinct tasks in invariant causal prediction:

  • (T1) When S⋆S^{\star} is identifiable, how can we accurately recover the entire causal parent set?

  • (T2) When S⋆S^{\star} is not fully identifiable, how can we identify a subset of S⋆S^{\star} while controlling false causal discoveries?

As shown in Table 1, existing approaches either do not explicitly perform variable selection or generally focus on only one of these two goals. To address both tasks, we introduce an invariance score that quantifies the degree of invariance of a predictor set SS, with smaller scores indicating greater invariance. For Task (T1), we incorporate this score as a regularization term in the risk minimization objective to encourage the selection of an invariant predictor set. We establish identifiability conditions for S⋆S^{\star} and show that the resulting estimator recovers S∗S^{*} under suitable regularity conditions. For Task (T2T2), we adopt the multiple testing framework of Martinet et al. [15]. Specifically, for each variable kk, we search for the minimum invariance score among all predictor sets that exclude kk. If even this minimum score is sufficiently large, it provides evidence that no invariant predictor set can exclude kk. Consequently, kk must belong to the intersection of all invariant predictor sets and hence to the true causal parent set S∗S^{*}. We further develop a multiplier bootstrap procedure to approximate the distribution of the minimum score and establish asymptotic type-I error control for false causal discoveries.

MethodGeneral interventionsTask 1Task 2ℓ0\ell_0-Var. selectionComputation
IRM✔✘✘✘continuous nonconvex
Causal Dantzig✘✔✘✘convex program
NegDRO✘✘✘✘nonconvex minimax
EILLS✔✔✘✔enumeration
CoCo✔✘✘✘continuous nonconvex
BIP✔✔✘✔enumeration
ICP✔only under ident.✔subset testingtt-test and FF-test
WVM✔only under ident.✔variable-wise testsWasserstein
Ours✔✔✔✔convex MIP

Table 1. Comparison of related work and our contributions. Note that ICP and WVM can recover S∗S^{*} only under identifiability.

Notably, both tasks involve optimization over discrete predictor subsets. To avoid exhaustive subset enumeration, we develop convex mixed-integer programming (MIP) formulations for the invariance score and its subsequent optimization problems. Subset selection is naturally represented through binary variables, and the resulting formulations have convex continuous relaxations, enabling efficient optimization and certificates of global optimality. Unlike existing approaches ICP, EILLS and BIP, our MIP framework allows the use of branch-and-bound algorithms that (i) efficiently prune candidate subsets to reduce the computational burden and (ii) return solutions with guaranteed optimality gaps below a prespecified tolerance. We further develop a scalable coordinate descent heuristic that efficiently finds solutions of high quality. When incorporated into the MIP framework, these solutions can be equipped with certificates of optimality gaps.

Our invariance score is constructed based on the least-squares coefficient and risk (LSCR) invariance principle for linear models. This principle requires both the population ordinary least squares (OLS) coefficients and the corresponding OLS risks to remain invariant across environments. Unlike Causal Dantzig and NegDRO, neither the linear structural causal model we consider nor the LSCR principle imposes specific restrictions on the intervention mechanisms, provided that the causal mechanism for the response remains unchanged. Moreover, tests based on the LSCR principle demonstrate greater statistical power than ICP and WVM in our experiments. This improvement can be attributed, in part, to the stronger invariance restrictions imposed by LSCR compared with tests on the regression residuals used in ICP, which can fail to detect changes in regression coefficients. In contrast, WVM involves a highly nonconvex optimization problem, making it susceptible to suboptimal solutions that can compromise its empirical performance. Our MIP framework can also be extended to settings with latent confounding by adopting a different invariance score.

Finally, we demonstrate the performance of our methods using both synthetic data and real data collected from a tightly controlled physical system. First, our estimator for Task (T1) achieves substantially higher accuracy in recovering causal parents than competing methods as the dimension increases. Second, our procedure for Task (T2) consistently achieves higher statistical power than competing methods while maintaining type-I error control. For both tasks, our methods remain computationally competitive.

The remainder of the paper is organized as follows. § 2 introduces the problem setup and the LSCR invariance principle. § 3 presents the MIP formulations for the invariance score and the two complementary tasks. Sections 4 and 5 investigate Task (T1) and Task (T2), respectively. Sections 6 and 7 evaluate the proposed approach through synthetic and real data experiments. Section 8 extends our framework to settings with nonlinear causal effects or hidden confounding. Finally, Section 9 discusses future research directions. The code for implementing our methods and reproducing the numerical experiments is available at https://github.com/Xiaozhu-Zhang1998/mip_inv_pred.

Other related literature

This section reviews three additional lines of related research not discussed earlier and highlights their connections to and distinctions from our proposed framework.

Distributional robustness and domain generalization. Beyond causal predictor selection, invariance has also been widely used to improve prediction under distributional shifts. One line of work focuses on identifying invariant predictor subsets that generalize to unseen environments. Rojas-Carulla et al. [20] study this problem in causal transfer learning, while Pfister et al. [19] combine regression models based on invariant predictor subsets to improve predictive performance across environments. Another line of work focuses on distributional robustness. Meinshausen and Bühlmann [16] introduce maximin effects for robust regression with heterogeneous data, while anchor regression (Rothenhäusler et al., [22]) and DRIG (Shen et al., [23]) aim to achieve robust prediction under distributional shifts caused by interventions. For probabilistic prediction, Henzi et al. [10] propose invariant probabilistic prediction (IPP), which uses proper scoring rules to encourage invariance of prediction risks across environments. While these approaches primarily aim to improve prediction under distributional shifts, our work focuses on identifying causal predictors through invariance across environments.

Beyond linear invariant prediction. Another line of work extends invariant causal prediction beyond linear models. Heinze-Deml et al. [9] develop nonlinear and nonparametric versions of ICP using statistical tests for invariance across environments. Kook et al. [12] extend ICP to general response types, including categorical, count, and censored outcomes, through transformation models. More recently, Gu et al. (2025) propose focused adversarial invariant regularization, which uses neural networks and adversarial optimization to identify invariant predictors in nonparametric regression models. These approaches extend invariant causal learning to more flexible model classes, whereas our work focuses on linear models to develop mixed-integer convex formulations with statistical and optimization guarantees. Nonetheless, we describe how our MIP formulations can be extended to handle nonlinear additive models in Section 8.

Mixed-integer optimization in statistical learning. Recent advances in mixed-integer programming have made combinatorial optimization increasingly practical for statistical learning. Bertsimas et al. [3] develop a mixed-integer optimization approach to best subset selection, using initial high-quality solutions to accelerate branch-and-bound algorithms. Bertsimas and Van Parys [4] further introduce a binary convex reformulation and cutting-plane algorithms for scalable ℓ0\ell_0-regularized regression. Hazimeh and Mazumder [8] develop efficient coordinate descent and local combinatorial search algorithms for best subset selection. Similar ideas have also been applied to other statistical problems, including multi-task learning (Behдин et al., 2026) and Bayesian network structure learning (Manzour et al., [14]). These studies demonstrate that exploiting problem structures can substantially improve the computational efficiency of discrete optimization. Convex mixed-integer programming has also been used to learn entire causal graphs (Küçükyavuz et al., [13]; Manzour et al. [14]; Xu et al. (2025); Zhang et al. [28]), although this is a substantially more challenging problem that typically requires modeling assumptions on the entire system of variables.

Notation

For a random variable ZZ with observations {Zi}i=1m\{Z_i\}_{i=1}^{m}, we define the empirical squared norm by ∥Z∥m2:=m−1∑i=1mZi2\lVert Z\rVert_m^2 := m^{-1}\sum_{i=1}^{m} Z_i^2. Similarly, for two random variables ZZ and WW with paired observations {(Zi,Wi)}i=1m\{(Z_i,W_i)\}_{i=1}^{m}, we define the empirical inner product by ⟨Z,W⟩m:=m−1∑i=1mZiWi\langle Z,W\rangle_m := m^{-1}\sum_{i=1}^{m} Z_iW_i. For any index set S⊆[p]S \subseteq[p] and random vector U∈RpU \in\mathbb{R}^{p}, we use US∈R∣S∣U_S \in\mathbb{R}^{|S|} to denote the subvector of UU indexed by SS. For a vector w∈Rpw \in\mathbb{R}^{p}, we use supp⁡(w)={j:wj≠0}\operatorname{supp}(w)=\{j:w_j\ne0\} to denote its support. Lastly, for two sequences ana_n and bnb_n, we write an≲bna_n\lesssim b_n if there exists a constant C>0C>0 and n0n_0 such that an≤Cbna_n\le Cb_n for all n≥n0n\ge n_0. We write an≳bna_n\gtrsim b_n if both an≲bna_n\lesssim b_n and an≳bna_n\gtrsim b_n hold. We write an=o(bn)a_n=o(b_n) if an/bn→0a_n/b_n\to0 as n→∞n\to\infty.

Setup: causality and invariant predictions from heterogeneous data

Linear structural causal model

We suppose we have access to observations of variables under different environments, such as experimental conditions in which some of the variables may have been manipulated, that is, received interventions. To represent this setting, we consider covariates X∈RpX \in\mathbb{R}^{p}, and response variable Y∈RY \in\mathbb{R}. The interventions on these variables take values in the set E\mathcal{E}; each e∈Ee \in\mathcal{E} represents a different environment that generates the random vector (Xe,Ye)(X^{e}, Y^{e}). We posit that for every e∈Ee \in\mathcal{E}, the covariates XeX^{e} and the response YeY^{e} are related via the following linear structural causal model (SCM) for some distribution F\mathcal{F}:

Ye=β⋆TXe+εe,supp⁡(β⋆)=S⋆,εe⊥XS⋆e,εe∼F,E[εe]=0.(1)Y^{e} = \beta^{\star\mathsf{T}} X^{e} + \varepsilon^{e}, \quad\operatorname{supp}(\beta^{\star}) = S^{\star}, \quad\varepsilon^{e} \perp X_{S^{\star}}^{e}, \quad\varepsilon^{e} \sim\mathcal{F}, \quad\mathbb{E}[\varepsilon^{e}] = 0. \tag*{(1)}

Here, β⋆∈Rp\beta^{\star} \in\mathbb{R}^{p} is a vector encoding causal relationships between the covariates and the response variable, namely βj⋆≠0\beta_{j}^{\star} \ne0 if covariate XjeX_{j}^{e} is a causal parent of YeY^{e} in the graph among (Xe,Ye)(X^{e}, Y^{e}). The subset S⋆⊆{1,2,…,p}S^{\star} \subseteq\{1,2,\ldots,p\} represents the covariates that are causal parents of YeY^{e}, and the coefficients βS⋆⋆\beta_{S^{\star}}^{\star} represent the strength of these causal effects. The SCM (1) thus posits that the structure and strength of the causal parents of YeY^{e} do not change across e∈Ee \in\mathcal{E}. The noise variable εe∈R\varepsilon^{e} \in\mathbb{R} is assumed to be independent of the causal parents XS⋆eX_{S^{\star}}^{e}. This independence condition corresponds to a causal sufficiency assumption, namely that there is no unobserved confounding simultaneously affecting the covariates and the response variable. In Appendix D, we discuss extensions to the setting with latent confounding. Importantly, εe\varepsilon^{e} can have dependencies with other coordinates of XeX^{e} outside the index set S⋆S^{\star}. Such dependencies are expected when some of the covariates are descendants of YY in the causal graph.

The condition that the distribution of εe\varepsilon^{e} remains the same across all e∈Ee \in\mathcal{E} means that the response variable does not receive a direct intervention, although its marginal distribution could still be changed due to interventions on its causal ancestors. Finally, the zero-mean condition on εe\varepsilon^{e} can be assumed without loss of generality, as a nonzero mean can be absorbed into the term β⋆TXe\beta^{\star\mathsf{T}} X^{e} by augmenting the covariates with a constant intercept variable. The parameter β⋆\beta^{\star} and the distribution F\mathcal{F} are not assumed to be known.

For every e∈Ee \in\mathcal{E}, we assume that we have nen^{e} independent and identically distributed observations of (Xe,Ye)(X^{e}, Y^{e}) from the SCM (1). We further assume that the samples are independent across environments.

LSCR-invariant prediction models

The SCM (1) exhibits important invariances that we highlight in this section. For any S⊆[p]S \subseteq[p] and e∈Ee \in\mathcal{E}, define

βe,S:=arg⁡min⁡β~∈Rp, supp⁡(β~)⊆S E[(Ye−β~TXe)2],νe,S:=E[(Ye−βe,STXe)2],(2)\beta^{e,S} := \underset{\widetilde{\beta} \in\mathbb{R}^{p},\ \operatorname{supp}(\widetilde{\beta}) \subseteq S}{\arg\min}\ \mathbb{E}\left[\left(Y^{e} - \widetilde{\beta}^{\mathsf{T}}X^{e}\right)^{2}\right], \qquad\nu^{e,S} := \mathbb{E}\left[\left(Y^{e} - \beta^{e,S\mathsf{T}}X^{e}\right)^{2}\right], \tag*{(2)}

as the population OLS solution when linearly regressing YeY^{e} on XSeX_{S}^{e}, and the corresponding risk. We propose the following invariance principle based on the OLS coefficients and risk.

References

  1. [1]Arjovsky, M., Bottou, L., Gulrajani, I. and Lopez-Paz, D. (2019), ‘Invariant risk minimization’, arXiv preprint arXiv:1907.02893.arxiv.org/abs/1907.02893
  2. [2]Behdin, K., Loewinger, G., Kishida, K. T., Parmigiani, G. and Mazumder, R. (2026), ‘Multi-task learning for sparsity pattern heterogeneity: statistical and computational perspectives’, Journal of the Royal Statistical Society Series B: Statistical Methodology 88(3), 1029–1059.DOI
  3. [3]Bertsimas, D., King, A. and Mazumder, R. (2016), ‘Best subset selection via a modern optimization lens’, The annals of statistics pp. 813–852.arxiv.org/abs/1507.03133
  4. [4]Bertsimas, D. and Van Parys, B. (2020), ‘Sparse high-dimensional regression: Exact scalable algorithms and phase transitions’, The Annals of Statistics 48(1), 300–323.arxiv.org/abs/1709.10029
  5. [5]Fan, J., Fang, C., Gu, Y. and Zhang, T. (2024), ‘Environment invariant linear least squares’, The Annals of Statistics 52(5), 2268–2292.DOI
  6. [6]Gamella, J. L., Peters, J. and Bühlmann, P. (2025), ‘Causal chambers as a real-world physical testbed for ai methodology’, Nature Machine Intelligence 7(1), 107–118.DOI
  7. [8]Hazimeh, H. and Mazumder, R. (2020), ‘Fast best subset selection: Coordinate descent and local combinatorial optimization algorithms’, Operations Research 68(5), 1517–1537.arxiv.org/abs/1803.01454
  8. [9]Heinze-Deml, C., Peters, J. and Meinshausen, N. (2018), ‘Invariant causal prediction for nonlinear models’, Journal of Causal Inference 6(2), 20170016.
  9. [10]Henzi, A., Shen, X., Law, M. and Bühlmann, P. (2025), ‘Invariant probabilistic prediction’, Biometrika 112(1), asae063.
  10. [11]Kamath, P., Tangella, A., Sutherland, D. J. and Srebro, N. (2021), Does invariant risk minimization capture invariance?, in ‘International Conference on Artificial Intelligence and Statistics’.arxiv.org/abs/2101.01134
  11. [12]Kook, L., Saengkyongam, S., Lundborg, A. R., Hothorn, T. and Peters, J. (2025), ‘Model-based causal feature selection for general response types’, Journal of the American Statistical Association 120(550), 1090–1101.
  12. [13]Küçükyavuz, S., Shojaie, A., Manzour, H., Wei, L. and Wu, H.-H. (2023), ‘Consistent second-order conic integer programming for learning bayesian networks’, Journal of Machine Learning Research 24(322), 1–38.
  13. [14]Manzour, H., Küçükyavuz, S., Wu, H.-H. and Shojaie, A. (2021), ‘Integer programming for learning directed acyclic graphs from continuous data’, INFORMS Journal on Optimization 3(1), 46–73.DOI
  14. [15]Martinet, G. G., Strzalkowski, A. and Engelhardt, B. (2022), ‘Variance minimization in the wasserstein space for invariant causal prediction’, in ‘International Conference on Artificial Intelligence and Statistics’, PMLR, pp. 8803–8851.arxiv.org/abs/2110.07064
  15. [16]Meinshausen, N. and Bühlmann, P. (2015), ‘Maximin effects in inhomogeneous large-scale data’, The Annals of Statistics 43(4), 1801–1830.
  16. [17]Park, Y. W. and Klabjan, D. (2017), ‘Bayesian network learning via topological order’, Journal of Machine Learning Research 18, 1–30.arxiv.org/abs/1701.05654
  17. [18]Peters, J., Bühlmann, P. and Meinshausen, N. (2016), ‘Causal inference by using invariant prediction: identification and confidence intervals’, Journal of the Royal Statistical Society Series B: Statistical Methodology 78(5), 947–1012.arxiv.org/abs/1501.01332
  18. [19]Pfister, N., Williams, E. G., Peters, J., Aebersold, R. and Bühlmann, P. (2021), ‘Stabilizing variable selection and regression’, The Annals of Applied Statistics 15(3), 1220–1246.arxiv.org/abs/1911.01850
  19. [20]Rojas-Carulla, M., Schölkopf, B., Turner, R. and Peters, J. (2018), ‘Invariant models for causal transfer learning’, Journal of Machine Learning Research 19(36), 1–34.arxiv.org/abs/1507.05333
  20. [21]Rothenhäusler, D., Bühlmann, P. and Meinshausen, N. (2019), ‘Causal dantzig’, The Annals of Statistics 47(3), 1688–1722.
  21. [22]Rothenhäusler, D., Meinshausen, N., Bühlmann, P. and Peters, J. (2021), ‘Anchor regression: Heterogeneous data meet causality’, Journal of the Royal Statistical Society: Series B (Statistical Methodology) 83(2), 215–246.DOI
  22. [23]Shen, X., Bühlmann, P. and Taeb, A. (2026), ‘Causality-oriented robustness: Exploiting general noise interventions’, Journal of the American Statistical Association 121(553), 704–715.arxiv.org/abs/2307.10299
  23. [24]Wang, Z., Hu, Y., Bühlmann, P. and Guo, Z. (2024), ‘Causal invariance learning via efficient nonconvex optimization’, arXiv preprint arXiv:2412.11850.arxiv.org/abs/2412.11850
  24. [27]Yin, M., Wang, Y. and Blei, D. M. (2024), ‘Optimization-based causal estimation from heterogeneous environments’, Journal of Machine Learning Research 25(168), 1–44.
  25. [28]Zhang, X., Keret, N., Shojaie, A. and Taeb, A. (2025), ‘Convex mixed-integer programming for causal additive models with optimization and statistical guarantees’, arxiv preprint arXiv:2511.21126.arxiv.org/abs/2511.21126

Paper details

vlnc:W_vudb3dt4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents