CS Paper Radar

The Lagrangian Structure of Cost-Penalized Active Feature Acquisition

Joseph Bingham

cs.LG ·submitted 2026-10-15 14:03 UTC · v1
theory

Abstract

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, and prove that A -> I(Y;X_A) need not be submodular, even for jointly Gaussian variables. This rules out a direct Nemhauser-Wolsey-Fisher bound; naive Bayes restores submodularity. We also bound the randomization gap between hard-budget and expected-cost optima, analyze sensitivity to dual-multiplier error under local smoothness, and derive a conditional CVAE generator-shift bound given a bound on forward predictive KL. We treat this KL as a diagnostic quantity, not as a transform of training loss. Experiments cover synthetic Gaussian settings, AFA benchmarks, and clinical differential diagnosis on MIMIC-IV. On MIMIC-IV, EIG-Cost achieves macro-F1 0.180 +/- 0.012 at a $30 budget, using 6.6% of full-panel cost.

Comment
52 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Towards optimal selection schedules for online active learning

cs.LG stat.MLcond-mat.dis-nn ·2026-10-16 ·Hugo Cui, Francesca Mignacco, Francesco Mori
similarity 0.60
Abstract

We consider the problem of online linear classification, where a stream of unlabeled samples is available, and annotation is costly. We investigate the optimal query policy, that prescribes whether and when a sample should be labeled and used for a training step, or instead discarded, so as to minimize a given objective. We focus on the realizable case, under Gaussian design, in the high-dimensional regime where data dimension and number of unlabeled samples grow proportionally. We consider two objectives: 1) the generalization error under a labeling budget, and 2) a cumulative cost function where mistakes have unit cost and queries cost $Δ$. We first show that the myopic policies that greedily minimize at all times the increment in the objective correspond to either small or intermediate-margin policies, that prescribe the selection of samples whose margins fall within certain intervals that shrink with time. Within this class, we numerically ascertain the optimal schedules for the selection thresholds that minimize the final values of the objectives. Taking inspiration from the myopic policy for the cumulative cost, we design a very simple query policy schedule that we compare to other proposed heuristics, on synthetic data and real medical image datasets. Finally, we discuss myopic policies for two-layer neural networks, and exemplify how naive margin-based policies can cease to be optimal.

0.27

Primal-Dual Representation Learning for Low-Rank Constrained MDPs

cs.LG ·2026-10-22 ·Chenhao Zhou, Chao Zhang, Wensong Bai, Hanbin Zhao, Hui Qian
top venuetheory similarity 0.59
Abstract · Accepted at NeurIPS 2026

Representation learning has substantially improved the efficiency of unconstrained continuous-state Markov Decision Processes (MDPs), but its extension to Constrained MDPs (CMDPs) is difficult because the transition representation must be learned while constraint violation is controlled. In this paper, we study representation learning for low-rank CMDPs with continuous state spaces, and propose REP-PD-TEG for the soft cumulative-violation setting. In the feature learning period, the algorithm interacts with the environment using a decaying-$ε$-greedy mixture execution policy, and uses the collected samples to learn transition features by maximum likelihood. Based on the learned features, it constructs uncertainty bonuses and plans with an optimistic Lagrangian objective to obtain the return policy. We prove regret and soft-violation guarantees for the return policies, and quantify the influence of the decaying-$ε$-greedy exploration. In particular, REP-PD-TEG achieves the optimal $\widetilde O(\sqrt K)$ return policy bound, and gives a $\widetilde O(K^{3/4})$ overall sample bound when exploratory actions are charged. For the stricter hard cumulative violation, where feasibility must be verified episode by episode, we propose REP-PD-H-TEG. It plans under a bonus-corrected lower-confidence utility certificate with the learned representation, and performs a stabilized dual search to obtain the return policy, yielding regret and hard-violation bounds. Together, these results give the first theoretically guaranteed representation-learning method for low-rank continuous-state CMDPs with both soft cumulative guarantees and certified hard-violation control.

0.24

Towards Certifiable State Estimation under Observability Degeneracy

cs.RO ·2026-10-14 ·Baoshan Song
theory similarity 0.57
Abstract

Certifiable optimization provides global optimality guarantees for non-convex state estimation in robotics. However, under severe physical sensing degeneracy, convex Semidefinite Programming relaxations solved via Interior-Point Methods suffer from rank expansion, rendering direct semidefinite solving and spectral rounding algebraically invalid. In this paper, we establish a universal candidate-driven dual certification framework that resolves this challenge without incurring rank expansion. First, from an epigraph perspective, we prove that while sensing degeneracy expands the primal optimal set into a flat equi-cost face, cost tightness and multiplier recovery remain strictly intact, enabling global verification without direct semidefinite solving. Second, we propose an observability-aware local search using solution remapping, coupled with a closed-form dual multiplier recovery scheme that executes in sub-microsecond latency. Third, we derive a model-specific adaptive dual safety threshold parameterized by the minimum non-zero eigenvalue of the observable Hessian and uneradicated residual leakage, preventing false rejections of optimal candidates under weak observability. We validate our universal framework with robust registration under degenerate measurements.

0.11

Does AI Help or Harm? Endogenous Information Acquisition with AI Advice

cs.GT econ.TH ·2026-09-28 ·Kexin Chen, Tao Lin, Jianwei Huang
published similarity 0.57
Abstract · Accepted by WINE 2026

AI advice increasingly enters human decision workflows before costly information acquisition and final action. This paper studies how such advice affects decision quality, measured by the gross utility of the final action. Advice shifts beliefs before the decision maker chooses an acquisition experiment with uniformly posterior-separable (UPS) costs. The analysis characterizes gross effects through the continuation gross value generated by net-optimal acquisition. Convexity of this value function is necessary and sufficient for every AI signal to weakly improve gross utility at every prior, while nonconvexity allows a binary signal to cause gross harm. The criterion gives tight state-space results. Every AI signal is weakly gross-improving in binary-state problems under arbitrary actions, payoffs, and UPS costs. A minimal three-state problem can generate gross harm through concentrated shutdown, where valuable acquisition stops. For classification problems with Shannon acquisition costs, the criterion becomes an active-set slope test. It guarantees weak gross improvement for homogeneous classification and all three-state weighted classification problems, while a minimal four-state failure arises from attention dilution, where acquisition shifts away from high-stake distinctions. Along a Blackwell-increasing mixture path, gross utility can first decrease and then increase. With endogenous interpretation, cheaper interpretation can reduce gross utility.

0.35

AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints

cs.LG ·2026-10-06 ·AbdAlRahman Odeh, Teng-Hui Huang, Hesham El Gamal
theory similarity 0.57
Abstract · 10 pages, 3 figures

Active Feature Acquisition (AFA) is a classification problem in which an agent decides which costly features to acquire before predicting each sample's label. Unlike batch AFA, which trains a fixed policy and classifier offline on fully observed data, online AFA updates its predictor from revealed labels as samples arrive. Existing online methods either use deep reinforcement learning (RL) without performance guarantees or maximize cost-adjusted reward rather than enforce a global budget. We formulate online AFA as a combinatorial Bandits with Knapsacks (BwK) problem that couples acquisition and prediction. Unlike prior bandit-based AFA and classical BwK, our setting has combinatorial complexity, evolving rewards, a global budget, and structured side information. We obtain an improved regret upper bound over standard BwK bounds in this framework, leveraging a cardinality-aware confidence bound and the subset update structure. To avoid an exponentially large action space, we propose \emph{LP-Chain}, a variant that searches a cost-aware chain of feature subsets with a size that grows linearly with the number of features. While the regret upper bound is specific to the combinatorial framework, \emph{LP-Chain} empirically achieves comparable predictive performance. On synthetic data, \emph{LP-Chain} outperforms HEDGE-based BwK and deep RL-based online AFA baselines and scales favorably to more features.

0.26

Cost-Aware Stopping for Freeze-Thaw Bayesian Optimization: When Does One-Step Lookahead Suffice?

cs.LG math.OCstat.ML ·2026-10-30 ·Long Vu, Jongseong Brad Choi, Binoy Ravindran, Zhoulai Fu
theory similarity 0.57
Abstract

Freeze-thaw Bayesian optimization (BO) evaluates candidates in resumable increments but usually stops at a budget or convergence test. We maximize a budget-free utility, the best observed score minus a cost per increment, with a one-step lookahead: advance the candidate with the largest expected improvement (EI) under a fixed surrogate, and stop once no EI exceeds the cost. This rule, EI stopping, never falls below stopping immediately in expected utility, yet it can stop too early. We construct a certificate, a lower bound on the value of two-step lookahead, that proves such a stop premature, and repeating this correction never lowers expected utility under the surrogate. Under the surrogate, EI stops are premature on average at low costs and lose little at high costs. On three hyperparameter optimization benchmarks, a pre-registered test finds EI stopping noninferior to the correction in most high-cost settings, while the correction gains at low costs on two of the three; more information sharing in the surrogate raises EI stopping's utility. On the surrogates of two published methods, EI stopping trades lower scores for fewer training increments. EI stopping is a simple cost-aware reference whose utility depends on the surrogate.

0.38

Low-Budget Active Learning through Entropic Optimal Transport

cs.LG math.OC ·2026-10-01 ·Rim Hajal, Mathieu Besançon, Jérôme Malick
similarity 0.56
Abstract

We consider low-budget active learning, which consists of selecting a limited number of points, the coreset, such that a model can be trained to high accuracy on the selection only. This problem is particularly relevant in contexts where labeling requires costly expert intervention, as in medical applications. We leverage features extracted from a pretrained self-supervised model to represent the data, and perform coreset selection directly in this feature space. In this paper, we use entropic optimal transport, specifically the Sinkhorn divergence, as the coreset selection criterion, which first allows us to get dimension-free sample complexity results, and second admits computationally efficient gradient evaluations. This opens the way to using gradient-based algorithms to rapidly compute solution candidates, further improved by a swap-based local search, with guarantees on the solution quality. Experiments on image benchmarks and medical datasets show that our method outperforms state-of-the-art heuristics in low-budget settings.

0.13

Rethinking Optimization Methods for Hierarchical Feature Selection

cs.AI ·2026-11-06 ·Xinyuan Song, Zekun Cai, Liang Zhao
code/data similarity 0.56
Abstract · Under review

Rare-event forecasting often depends on interpretable conjunctions: a single keyword, location, or temporal cue may be weak, while their joint occurrence can identify a meaningful precursor. Hierarchical-Task Numerical conjunctive feature Learning (HTNL) selects Numerical Conjunctive Features (NCFs) through a structured sparsity objective. However, the resulting optimization problem is challenging, making optimization design critical to its practical performance. We give a unified diagnosis of four HTNL optimization families: original majorization-minimization (MM), variational quadratic form (VQF), alternating direction method of multipliers (ADMM), and weighted group lasso (WGL). Our analysis distinguishes three key factors that jointly determine HTNL optimization behavior. First, VQF and MM are algebraically equivalent under matched variational updates and optimize a squared-penalty formulation. Second, ADMM optimizes the unsquared objective through consensus splitting; we replace its truncated FISTA proximal solver with a scalar bisection update (ADMM-Bisect) for more accurate treatment of near-threshold blocks. Third, WGL targets the same unsquared objective, while all methods face rapidly decaying active-set admission scores. Across two synthetic datasets and 11 civil-unrest and flu-surveillance tasks, VQF achieves the highest mean AUC with the most compact non-collapsing supports. ADMM-Bisect reduces measured runtime, while calibrated WGL avoids the empty-support failures of its original scale. Synthetic results further show how proximal accuracy, pruning, and search budget affect candidate recovery, especially for longer conjunctions. Code will be made publicly available upon publication.

0.34