The Lagrangian Structure of Cost-Penalised Active Feature Acquisition

Active Feature Acquisition (AFA) sequentially selects which features to measure to maximise predictive accuracy under a budget. A widely-used heuristic scores each candidate feature $j$ by its Expected Information Gain minus a cost penalty, $\EIG(j \mid x_{\calS}) - \lambda c_j$, and acquires greedily. We call this rule \emph{EIG-Cost}. No theoretical justification for this formulation has been given in the literature. We show that $\calA \mapsto I(Y; X_{\calA})$ fails to be submodular even for jointly Gaussian distributions, which rules out any direct application of the classical $(1{-}1/e)$ approximation guarantee for greedy submodular maximisation. Nonetheless, EIG-Cost coincides at every step with the greedy maximiser of the Lagrangian-relaxed budget-constrained AFA objective, with $\lambda$ playing the role of the budget dual variable. Under local strong concavity of the value function $V(b)$, we obtain a quadratic $\lambda$-sensitivity bound. We characterise the departure from submodularity via the submodularity ratio and measure it empirically on a large clinical dataset (MIMIC-IV, 40{,}595 patients, 21-class differential diagnosis), where we find $\gamma \geq 0.97$ on average, so the theoretical guarantees apply with only a small penalty.