ResearchResearch paperComputer Vision · Large Language Models · Interpretability1 source · Oct 15, 2026

The Lagrangian Structure of Cost-Penalized Active Feature Acquisition

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|xS)-lamcj (EIG-Cost), but its theoretical guarantees are unclear.
Our analysis identifies EIG-Cost as one-step greedy optimization of the Lagrangian relaxation of expected-cost AFA, with lam as its dual multiplier.
Supporting results establish an adaptive chain-rule identity showing that cumulative stepwise EIG optimizes transcript information, and prove that A -> I(Y;XA) need not be submodular, even for jointly Gaussian variables.
Experiments cover synthetic Gaussian settings, AFA benchmarks, and clinical differential diagnosis on MIMIC-IV.

[1]The Lagrangian Structure of Cost-Penalized Active Feature Acquisition
arXiv (AI, ML, NLP, CV, robotics, multi-agent) · Oct 15, 02:03 PM
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.

Extractive summary: sentences quoted from the sources.

Before this