Robust Contextual Optimization with Missing Covariates

Summary

This paper studies contextual stochastic optimization (CSO) under the practically pervasive nuisance of partially missing covariates. Where prior CSO work assumes fully observed contexts, and where two-stage impute-then-optimize pipelines suffer from imputation error that is uncoupled from the downstream decision cost, the authors propose a distributionally robust formulation that operates directly on the partial data. The conceptual move is to build a latent ambiguity set of joint laws whose induced observable distribution — after being pushed through some Missing-at-Random (MAR) missingness kernel — is close (in KL, or, for continuous outcomes, in a Lévy–Prokhorov-projected KL) to the empirical partial-observation law. This encodes the missingness mechanism inside the estimation problem rather than repairing the data first, and lets the ambiguity radius do double duty as a hedge against both sampling error and the identification loss induced by missingness. Tractable convex reformulations are derived through change-of-variable and lifting/perspective arguments, and dual representations yield finite-sample out-of-sample disappointment bounds along with almost-sure consistency of value and optimizer as $n$ grows. A row-generation / column-on-demand scheme keeps the reformulation size governed by the latent support rather than the sample size. Empirically, a contextual newsvendor study over $R=100$ replications shows that MAR-KL DRO delivers lower out-of-sample cost and higher reliability than complete-case, complete-feature, and three impute-then-optimize baselines across sample sizes and missingness intensities. Overall the contribution is clearly framed and the tractability results are non-trivial. The main limitations are conceptual and empirical rather than technical-in-the-large: the framework rests essentially on the MAR assumption, whose violation is never stress-tested; the empirical study is confined to a single synthetic newsvendor DGP with a small discrete covariate space; the promised continuous-covariate case is explicitly deferred; and several key proof steps and definitions are underspecified or contain propagation-worthy typos that could obscure the tightness of the stated guarantees.

Strengths

• Conceptual contribution. Integrating the MAR missingness mechanism directly into a DRO ambiguity set — rather than imputing first and optimising second — is a clean and, to our knowledge, novel angle within the CSO literature. Definition 2.6 and Proposition 3.2 make the construction precise: the latent laws that survive are exactly those whose observable pushforward through some MAR kernel matches the empirical partial law within a KL radius.
• Tractability. The change-of-variables $v=p/(d^\top p)$, $t=1/(d^\top p)$, $u=Tp/(d^\top p)$ and the perspective form for $t\log(t/u)$ turn the linear-fractional inner problem into a convex conic program (Prop 3.5), and the dual (Theorem 3.6) is directly implementable in a conic solver. The extension to continuous outcomes via a binned LP-projected KL preserves this structure.
• Statistical guarantees. Theorem 3.7 delivers a genuine non-asymptotic out-of-sample disappointment bound with exponentially decaying failure probability, and Theorem 3.8 upgrades this to almost-sure consistency of value and optimizer via a summable-$\eta_n$ Borel–Cantelli argument. Theorem 3.15/3.16 replay the same programme in the continuous-outcome setting under a sieve.
• Scalability engineering. The aggregation argument (Appendix D.1) reduces the problem size to the number of distinct observations, and the row-generation scheme in D.3.1 makes the latent-support cost graceful — Table 2 shows the method reaching latent supports of $10^6$ where the flat reformulation stalls at $10^4$.
• Comprehensive experimental protocol. Appendix E specifies the DGP, six baselines, a $30$-point log-scale radius grid, a $25/75$ holdout tuning rule with a documented tie-breaking convention, an oracle-radius diagnostic, $R=100$ replications, Wilson intervals for reliability, and a $10^5$-sample out-of-sample evaluation. Reliability is reported alongside cost throughout.

Weaknesses

• MAR assumption is central and untested empirically. MAR is untestable from observed data, and every finite-sample and asymptotic result depends on it. Yet Appendix E.2 generates the mask by construction from a logistic MAR mechanism, so the theoretical assumption is guaranteed to hold in every reported experiment. The reader cannot tell how quickly performance degrades under a mildly MNAR mask, which is precisely the regime the motivating examples (executive/student income) live in.
• Empirical scope is narrow relative to the theoretical breadth. The abstract's 'various data geometries' claim is validated on a single problem (contextual newsvendor with piecewise-linear cost), a single DGP (mixture of two truncated discrete normals), a small discrete covariate space ($|\mathcal X|=27$, $|\mathcal Y|=13$), and a MAR mechanism whose parameters are chosen by the authors. No second application, no non-convex cost, and no real-world dataset with actual missingness appears.
• Continuous-covariate case explicitly deferred. Contribution (iii) advertises reformulations for continuous covariates, but Appendix D.4 delivers only a construction sketch and closes with 'A detailed treatment of these results would require substantial additional technical work and is therefore not included in this paper.' No tractable reformulation, no statistical guarantee, and no experiment for this case is provided. This materially narrows the delivered contribution.
• Overstated coverage / monotonicity. The main text claims Theorem 3.7 gives coverage 'for every sample size $n$' at level $1-\eta$; this is a fixed-$n$ inequality, not a uniform-in-$n$ guarantee. Separately, Theorem 3.8's $\hat\Phi_n \downarrow \Phi^*$ arrow asserts monotone convergence from above, but the appendix only argues convergence in both directions — monotonicity requires nested ambiguity sets, which is not established. These are small but real overstatements.
• Multiple load-bearing proof gaps. The sufficient-inclusion direction of Proposition 3.11 skips the marginal-mass re-multiplication that turns a conditional radius $2\delta/q_1$ into the joint $3\delta$ budget. The sieve contraction in the proof of Theorem 3.16 contains a sign inconsistency in $E_{f^*}[Z_{n,i}]$ (the ratio inside the log and inside $D_{\mathrm{KL}}$ do not agree) and a summability line whose exponent on $n$ is positive where a negative one is required. Case 2 of the Proposition 3.12 dichotomy is printed with the same condition as Case 1, making the split non-exhaustive. The empirical-MAR-kernel substitution (used repeatedly in the C.5 and C.11 proofs) claims KL non-increase 'as we previously showed' but the earlier occurrence only asserted the same non-increase.
• Notational and definitional slips. The transformation from the observable KL radius $\epsilon$ (Def 2.6) to the transformed radius $\gamma$ (Prop 3.2) is never stated in the main text; Theorem 3.6 opens 'For any $\epsilon>0$' but its body uses $\gamma$. The constants $L^\star_0$ (used in Remark 3.4) are never defined in the shown text. Table 5 lists $D_{\mathrm{BinPKL}}$ but describes it with the definition of $D_{\mathrm{PKL}}$ and drops the sieve argument $J$. A 'dual of Theorem 4' reference in Appendix D.3.2 is stale (theorems are numbered $3.x$). The reliability definition in Section 4 literally says the frequency with which realized cost exceeds the in-sample value — the opposite of its usage everywhere else.
• Weak imputation baselines. All three impute-then-optimize baselines use the same MLE-under-MAR imputer (parametric family unnamed), differing only in the downstream optimisation model. Appendix B.1 devotes multiple paragraphs to MissForest, MIWAE, GAIN, optimal-transport imputers, and multiple imputation, but none are used empirically. Beating a simple MLE imputer at small $n$ is unsurprising; a more informative benchmark would swap in a stronger imputer while keeping the downstream DRO fixed.
• Positivity assumption bites in the informative regime. Assumption 2.2 and Proposition 3.3's attainability condition require $p_X(\bar x)\ge\epsilon_0>0$ at the target context. The very high-dimensional, heterogeneously-observed contexts that motivate the paper are precisely those where a specific $\bar x$ may not appear in the sample. The deferred continuous-covariate kernel-smoothing sketch (D.4) is where this would be addressed, but it is not delivered.
• Missing statistical significance on cost claims. Reliability is reported with Wilson intervals; the cost comparison in Table 6 and Figure 4 is reported with mean and 20-80% quantile bands, without a paired-difference significance test. At $n\ge 2000$, several imputation baselines' relative cost is within a few percent of MAR-KL DRO — a paired sign / Wilcoxon test would let the reader gauge which differences are real.

Reproducibility & code

The veritas assessment reads the released materials and finds most headline claims backed by fully specified experiments (Appendix E.1–E.7 supplies the DGP, six baselines, tuning grid, holdout rule, reliability definition, and $R=100$ replications). At the same time, several concrete gaps make exact numerical reproduction harder than it needs to be:

• Headline aggregates. The dominance of MAR-KL DRO on out-of-sample cost and reliability (Tables 6, 7; Figures 4-9) is qualitatively reproducible from the specified pipeline. Reproducibility risk is judged low for the qualitative pattern and low-to-medium for the exact point estimates, because random seeds are not disclosed and the imputer used inside the three impute-then-optimize baselines is only sketched ('MLE under a MAR model') — its parametric family, EM/optimizer, and initialisation are unstated, and the exact percentages in Table 6 and reliability numbers in Table 7 will drift by a few points across independent reimplementations.
• Solve-time tables. The scalability results (Tables 1, 2) depend on hardware (CPU / RAM / thread count), MOSEK version, and warm-starting behaviour, none of which are disclosed. The paper says only 'we solve all conic reformulations with MOSEK using default feasibility/optimality tolerances.' The structural claims — that MAR-KL DRO is nearly flat in $n$ at fixed latent support, and that separation lifts the reachable support from $10^4$ to $10^6$ — are consequences of the reformulation and should reproduce directionally; the absolute seconds will not.
• Separation subproblem not fully displayed. The main-text description of the separation oracle ('the separation oracle solves, for each $y\in\mathcal Y$,') trails off before the objective is shown, and Appendix D.3.1 describes the loop without displaying the subproblem. This is the operation that produces the impressive Table 2 speedups and should be shown explicitly for a reader to reimplement it.
• Reference and evaluation infrastructure not documented. The reference optimum $z^*$ used in Figures 5 and 8 is not tabulated (a reproducer must compute it from the mixture DGP), the seeding protocol across the $R=100$ replications is not stated for the cost tables (only for reliability, in E.6), and whether the $10^5$-sample evaluation batch is redrawn per replication is left implicit.
• Continuous-outcome/covariate machinery unexercised. The sieve mesh schedule $J(n)$ that must satisfy both $h_{J(n)}n^\alpha\to 0$ and $J(n)\log n/n\to 0$ (Theorem 3.16) is not accompanied by any experimental exercise, so the practical sieve behaviour is not demonstrated.

Recommended Changes

Essential

• Add a MAR-violation robustness experiment. Reuse the newsvendor DGP but generate the mask under a mild MNAR mechanism (mask depends on the concealed $X_m$) and re-run the comparison against the same six baselines. Report degradation of MAR-KL DRO alongside baselines under this misspecification — directly addressing the MAR-untested weakness.
• Broaden the empirical scope. Add a second application — for example, one of the motivating cases (battery arbitrage) or a portfolio problem with a quadratic cost — and, if possible, one real-world dataset with genuine missingness. This is the most impactful way to substantiate the 'consistently outperforms' abstract claim across data geometries.
• Fix the load-bearing proof gaps. In Proposition 3.11 spell out the marginal re-multiplication step ($q_1 \cdot 2\delta/q_1 = 2\delta$ plus the $\delta$ marginal shift $\Rightarrow 3\delta$). In the sieve contraction proof of Theorem 3.16 correct the ratio orientation so that $E_{f^*}[Z_{n,i}]=-D_{\mathrm{KL}}(f^*\|f_{b^*_n})$ is consistent with $Z_{n,i}$'s definition, and fix the exponent in the summability line so the series is actually summable. In Proposition 3.12's case split, change Case 2 to $S_{\mathrm{obs}}\cap Y_{j_\infty}\neq\emptyset$. Convert the repeated empirical-kernel-KL-non-increase claim ('as we previously showed') into a self-contained lemma.
• Either deliver or rescope the continuous-covariate contribution. Move the deferred Appendix D.4 material into the paper with a real reformulation and guarantee, or rewrite contribution (iii) to advertise only what is delivered (discrete covariates; discrete or continuous outcomes).
• Correct the reliability definition and the 'every $n$' phrasing. Replace 'the empirical frequency with which the realized cost exceeds its in-sample counterpart' with the intended 'does not exceed' (matching Theorem 3.7 and every downstream usage). Replace 'the true latent joint distribution is guaranteed to lie inside the ambiguity set for every sample size $n$' with 'for each fixed $n$', or explicitly invoke the summable-$\eta_n$ Borel-Cantelli argument.

Suggested

• State the $\epsilon\!\to\!\gamma$ radius transformation and define $L^\star_0$ in the main text. A single sentence after Proposition 3.2 fixing $\gamma(\epsilon)$ and reserving one symbol per role would remove a persistent reading friction, as would giving $L^\star_0$ an explicit definition to match its use in Remark 3.4.
• Change $\hat\Phi_n \downarrow \Phi^*$ to $\hat\Phi_n \to \Phi^*$ in Theorem 3.8 unless nestedness of the ambiguity sets is proved, and echo the change in the abstract/introduction if it appears there.
• Display the separation subproblem explicitly in Section 4 (and again in Appendix D.3.1) so the row-generation scheme underlying Table 2 is reproducible from the paper text.
• Fix the 'constraints with $X=\bar x$ ... constraints with $X=\bar x$' typo so the second occurrence reads $X\neq\bar x$.
• Fix the stale 'dual of Theorem 4' reference in Appendix D.3.2 and sweep for other stale labels.
• Repair Table 5 to describe $D_{\mathrm{BinPKL}}$ correctly (sieve-parametrised binned PKL, with the $J$ argument) and separately for $D_{\mathrm{PKL}}$.
• Clean up the Hölder / bin-width notation in the C.11 proof so $\omega_p$ appears consistently and either $h_J$ or $h_n$ is used throughout for the bin diameter.
• Add stronger imputation baselines. Report Impute+DRO variants that use MissForest or a multiple-imputation aggregator (already discussed in Appendix B.1) as the imputer, keeping the downstream DRO fixed. This directly addresses the 'weak baselines' concern.
• Add a paired significance test on cost differences (paired sign, Wilcoxon, or bootstrap CI on the relative cost increase) so Table 6 and Figure 4 report whether MAR-KL DRO's advantage is statistically significant at each $n$.
• Report hardware and MOSEK version with Tables 1 and 2 so the absolute solve-times are reproducible, and expose the separation initialisation / warm-start behaviour.
• Publish seeds and the reference $z^*$. State the seeding protocol for the cost tables (matching E.6's statement for reliability) and either tabulate the population optimum $z^*$ or supply the code that computes it from the mixture DGP.
• Substantiate the 'robust to context choice' parenthetical with a supplementary figure aggregating Experiment III across the 27 contexts, or drop the parenthetical.
• Add a worked example of the sieve schedule $J(n)$ that satisfies both conditions of Theorem 3.16, so a practitioner can instantiate the continuous-outcome method.
• Sketch (not just claim) the missing-outcome extension in D.2 — a paragraph modifying Theorem 3.7 for this case would suffice, replacing 'we omit the proofs for brevity'.