The Lagrangian Structure of Cost-Penalized Active Feature Acquisition

Joseph Bingham

Active Feature Acquisition (AFA) sequentially selects features to maximize predictive accuracy under an acquisition budget. A natural heuristic greedily maximizes Expected Information Gain minus a cost penalty, EIG(j|x_S)-lam*c_j (EIG-Cost), but its theoretical guarantees are unclear. We provide an a-posteriori certificate decomposing the gap to the optimal hard-budget policy into a budget-slack term and a greedy-suboptimality term Del_lam. The certificate is computable when the penalized optimum is tractable; on small heterogeneous-cost instances, we verify it exactly, finding Del_lam near zero across 4,000 solved cases. On the large clinical task, Del_lam is not computable, so the decomposition is diagnostic rather than a numerical guarantee. Our analysis identifies EIG-Cost as one-step greedy optimization of the Lagrangian relaxation of expected-cost AFA, with lam as its dual multiplier. For equal costs, we prove Del_lam <= exp(-gam*I(Y;X_[d])), where gam is the submodularity ratio, yielding a structural guarantee in the near-submodular regime. Supporting results establish an adaptive chain-rule identity showing that cumulative stepwise EIG optimizes transcript information,…