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.
Related
- On tractability, complexity, and mixed-integer convex programming representability of distributionally favorable optimization
- Non-convex integer programming: a deterministic solution method of the large block sale problem
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
- Learning to Solve Mixed-Integer Nonlinear Programming with Neural Networks and Sequential Quadratic Programming Refinement
BibTeX
@misc{zhang2026convex,
title = {{Convex Mixed-Integer Programming for Invariant Predictions from Multi-environment Data}},
author = {Xiaozhu Zhang and Rahul Mazumder and Armeen Taeb},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38942},
eprint = {2610.38942},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38942},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Convex Mixed-Integer Programming for Invariant Predictions from Multi-environment Data
AU - Xiaozhu Zhang
AU - Rahul Mazumder
AU - Armeen Taeb
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38942
UR - https://arxiv.org/abs/2610.38942
AB - 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.
ER -