Introduction
Modern decision-making increasingly relies on contextual features (covariates) to improve optimization under uncertainty. In Contextual Stochastic Optimization (CSO), decisions—such as inventory planning or battery scheduling—are made based on observed features that help predict uncertain outcomes. However, most existing models rely on a fragile assumption: that historical data is perfectly observed.
In reality, data is rarely perfect. Sensor failures, incomplete surveys, and heterogeneous data sources frequently result in partially missing covariates. Standard approaches to this problem typically involve either deleting incomplete records (Complete-Case Analysis) or using predictive models to guess the missing values before optimization (imputation). This paper introduces a distributionally robust framework that bypasses the traditional "impute-then-optimize" pipeline, offering stronger theoretical guarantees and superior empirical performance.
The Flaw in "Impute-then-Optimize"
The authors argue that two-stage "impute-then-optimize" pipelines are fundamentally flawed because the imputation step is entirely "decision-blind." The imputation model attempts to minimize statistical error without considering the downstream cost function of the optimization task. Consequently, decisions can become highly sensitive to imputation errors, particularly when the missingness itself introduces a distributional shift. Instead of treating missing data as a pre-processing hurdle, the authors propose treating it as a core component of the uncertainty model.
Methodology: An Integrated DRO Approach
To address the shortcomings of imputation, the paper proposes a novel Distributionally Robust Optimization (DRO) approach that exploits incomplete covariates to produce robust decisions directly.
Latent Ambiguity Sets
Rather than committing to a single imputed dataset, the framework defines a "latent ambiguity set." This set encompasses all possible joint distributions (latent laws) that could have generated the observed, incomplete data under a Missing at Random (MAR) mechanism. By explicitly encoding the MAR structure, the model ensures that candidate distributions are statistically consistent with how the data went missing. The optimizer can then "hedge" against the specific missing values that would incur the highest costs if guessed incorrectly.
Handling Different Data Geometries
The framework is adaptable to both discrete and continuous data:
- Discrete Case: For discrete features and outcomes, the authors utilize Kullback-Leibler (KL) divergence to define the ambiguity set. They successfully transform a complex, non-convex fractional problem into a tractable convex program using lifting and dualization techniques.
- Continuous Case: Because standard KL divergence can be brittle with continuous data, the authors introduce an LP-projected KL divergence. This novel metric combines the statistical properties of KL divergence with the geometric robustness of the Lévy-Prokhorov (LP) metric (a relative of the Wasserstein distance).
Computational Efficiency
A major technical contribution of the paper is a restricted-master separation scheme. Because the problem's complexity scales with the size of the data's support rather than the number of samples, the authors can solve instances with support sizes up to $10^6$ atoms by generating constraints on-the-fly.
Empirical Validation
The authors evaluate their method using the Contextual Newsvendor Problem, a classic operations research benchmark. They generated synthetic features and outcomes using mixtures of truncated normals to simulate complex contexts, and applied a logistic MAR mechanism where the probability of a feature being missing depends on other observed variables.
Experiments ranged from small datasets ($n=100$) to large-scale scenarios ($n=33,750$), testing missingness proportions from 20% to 80%.
Key Results
- Superior Out-of-Sample Performance: The proposed "MAR-KL DRO" consistently achieved lower out-of-sample costs compared to state-of-the-art imputation-based DRO methods, such as Wasserstein-DRO or KL-DRO applied to imputed data.
- High Reliability: The proposed method reliably met its own predicted cost targets even as the proportion of missing data increased. In contrast, baselines like Complete-Case Analysis collapsed under high missingness.
- Asymptotic Optimality: The authors provide finite-sample out-of-sample guarantees (a "disappointment bound"). Both theoretically and empirically, the robust decision converges to the "Oracle" decision—the optimal choice made with perfect data—as the sample size grows.
- Speed: Thanks to the separation scheme, the model solves high-dimensional problems in seconds, whereas naive full formulations fail to terminate.
Limitations and Future Directions
While the proposed framework represents a significant step forward, it assumes data is Missing at Random (MAR). It does not yet handle Missing Not at Random (MNAR) scenarios, where the probability of missingness depends on the unobserved value itself. Additionally, while the support-based scaling is highly efficient for large sample sizes, extremely high-dimensional feature spaces could still introduce a curse of dimensionality. Finally, for continuous covariates, the method relies on kernel smoothing; optimizing the choice of kernel and bandwidth remains an open area for future research.
Summary updated