Many prediction systems can pay to observe features one at a time: a clinician orders lab tests, a detector reads out sensor channels, a recommender queries user attributes. The standard recipe is greedy: buy whichever single feature most reduces expected error, then repeat. The recipe is attractive because, when features have diminishing returns, greedy selection is provably within a constant factor of the best possible subset. It also fails completely when features are synergistic, meaning two measurements are useless alone but decisive together, as in an XOR pattern. Recent work responds by giving up guarantees altogether. It either samples thousands of random subsets or trains lookahead policies. We propose a middle path. Greedy selection over small blocks of features keeps a provable guarantee whose strength is set by a measurable "synergy order." The price of that change is a search over the much larger space of possible blocks. We pay it with the budget-concentration trick from adaptive sensing: spend coarse effort on every candidate, discard the losers, and refine the rest.
In two sentences: treat the search for the next block of features to buy as a needle-in-a-haystack detection problem, where most candidate blocks have near-zero value and a few carry large joint value. Then use distilled sensing, which repeatedly discards candidates that look like noise and concentrates effort on survivors, to find those blocks with far fewer expensive gain estimates than scoring every block, while keeping a greedy-style approximation bound.
Core Claim
Let $f(S)$ be the expected reduction in prediction loss from observing feature set $S$ for the current instance, minus nothing else (costs enter separately). We define the order-$r$ submodularity ratio
$$\gamma_r = \min_{S,\,T} \frac{\sum_{B \subseteq T,\ |B| \le r} \big[f(S \cup B) - f(S)\big]}{f(S \cup T) - f(S)},$$
where $S$ is the set already observed and $T$ is any candidate set to add. The ratio $\gamma_r$ asks how much of the joint value of $T$ is visible through its blocks of size at most $r$. On a pure pairwise XOR problem $\gamma_1 = 0$ but $\gamma_2$ is bounded away from zero. For ordinary diminishing-returns objectives, $\gamma_1 \ge 1$.
We will prove that greedy selection over blocks of size $\le r$ achieves $f(S_k) \ge (1 - e^{-\gamma_r / r})\, f(S^*) - k\varepsilon$ against the best budget-$k$ set $S^*$, where $\varepsilon$ is the per-step error in estimating block gains. The $1-e^{-\cdot}$ form comes from the standard greedy recurrence in the influence-maximization analysis of Maximizing the spread of influence through a social network. In that recurrence each greedy block recovers at least a $\gamma_r/(r k)$ share of the remaining gap, and estimation error adds linearly per step. The exact constants are what the theory work must settle.
The second half of the claim is algorithmic. Scoring all $\binom{d}{r}$ blocks accurately is what makes block greedy impractical at $d = 784$. Distilled sensing (Haupt et al., analyzed in Haupt et al.) and sequential thresholding (Malloy) show that multi-stage elimination can localize sparse signals whose strength is far below what uniform effort allocation needs. Uniform allocation needs signal growing like $\sqrt{\log n}$; distilled sensing succeeds with signal growing arbitrarily slowly. Here the "signal" is the gain of a block, and the "measurement energy" is the number of Monte Carlo or nearest-neighbor draws used to estimate that gain. Block gains are nonnegative. That fits the one-sided hypotheses distilled sensing was built for, which the file lists as a limitation in other settings.
Relation to Prior Work
The motivating evidence comes from active feature acquisition. Acquisition Conditioned Oracle for Nongreedy Active Feature Acquisition makes three moves. It shows one-step greedy stalls on synergistic features, estimates conditional feature distributions with a $k$-nearest-neighbor model over the training pool, and picks subsets by scoring 10,000 random draws. We reuse its nearest-neighbor gain estimator as our oracle. We replace its random subset search with structured block greedy that carries a bound.
Learning-To-Measure meta-trains a Transformer that picks features by conditional mutual information and adds a multi-step lookahead to escape synergy. It provides no approximation ratio. We target the same failure with an explicit, estimable quantity ($\gamma_r$) instead of learned lookahead.
On the adaptive-sensing side, Info-greedy sequential adaptive compressed sensing shows that bisection search and top-eigenvector projection are information-greedy. It works one measurement at a time under Gaussian or mixture priors, gives no guarantee in the mixture case, and does not handle synergy. Compressive binary search shows adaptive bisection needs signal about 1.8x smaller than orthogonal matching pursuit. We borrow the elimination logic of these methods, not their measurement model.
Deep probabilistic subsampling learns a task-specific but fixed pixel mask. It is the natural non-adaptive reference point.
Submodular batch selection for labeling, as in SIMILAR and CRAIG (Coresets for Data-efficient Training), supplies the template of "greedy with a guarantee on a designed objective." Both assume diminishing returns and work over samples rather than features, so neither addresses synergy.
We are aware that ratio-based relaxations of submodularity exist in the broader literature. Our contributions are the block-order version, its estimation from data, and the pairing with distilled search. Adaptive-policy guarantees in the style of Non-Monotone Adaptive Submodular Maximization are the target for extending the per-step bound to the fully adaptive case.
Research Program
The algorithm starts at $r = 1$ and runs distilled search over singletons. It escalates to $r = 2$, and to $r = 3$ only on small $d$, when the best surviving singleton gain falls below a threshold. That trigger is a "dead-zone" detector, so synergy search is paid for only where diminishing returns break.
Each distillation stage gives every surviving block $m_t$ gain-estimate draws, keeps blocks above the median or above a noise-calibrated threshold, and doubles $m_t$. The chosen block is bought if its estimated gain per unit cost exceeds a stopping rule.
The theory work has three parts. First, prove the block-greedy bound with estimation error. Second, bound the number of gain-oracle calls distillation needs to reach per-step error $\varepsilon$ with high probability, in terms of how many blocks carry non-negligible gain. Third, give a finite-sample estimator of $\gamma_r$ on the training pool, so that each benchmark comes with a data-dependent certificate rather than a worst-case one.
Baselines
The naive reference points are uniform random feature acquisition and a fixed global feature ranking. We also include the static learned mask of DPS. On MNIST it reports 6.6% classification error with about 25 retained pixels, against 28.6% for uniform subsampling. We will run DPS at matched pixel budgets. Beating it at 25 pixels would show that per-instance adaptivity adds value beyond a well-learned fixed mask.
The strongest existing method is AACO from ACO. It is the closest in spirit, uses the same nearest-neighbor oracle we adopt, and reports the headline result that AACO matches the full-information decision "over 90% of the time while only requiring 20 out of 65 possible features" on the Open Bandit Dataset. The file reports no numeric AACO accuracy on MNIST, Gas, or Grid, so we will reproduce AACO ourselves. Both methods will share the same oracle, the same training pool, the same feature budgets, and a matched count of oracle calls, with AACO's subset-draw count swept upward so it is not handicapped.
Beating AACO means one of two things: equal or better accuracy-versus-features curves with at least several times fewer oracle calls, or higher Open Bandit agreement than 90% at 20 features under equal oracle calls.
L2M is the second strong competitor. It is run with its lookahead variant on the tabular tasks where it was evaluated (Metabric, MiniBooNE, MIMIC-IV), using its published setup. The file reports no L2M numbers, so we reproduce it.
One-step greedy (GDFS-style) with the same oracle isolates the benefit of blocks.
The key ablation is block greedy with uniform allocation of gain estimates across all candidate blocks, matched in total oracle calls. It isolates distillation. If uniform block greedy matches our method at equal calls, the adaptive-sensing ingredient contributes nothing.
Why not just…?
Why not just keep AACO's random subset sampling and add more draws? Random draws find a synergistic pair with probability that shrinks as the number of pairs grows, roughly quadratically in $d$. They also give no certificate. The real threat is that on moderate $d$, such as Gas, Grid, or 65-feature Open Bandit, enough draws simply work. Our oracle-call-matched comparison settles this. If AACO matches us at equal calls on those datasets, our claimed advantage shrinks to the guarantee and to high-$d$ settings like MNIST, and we will report it that way.
Why not just learn a lookahead policy as L2M does? Learned lookahead can resolve synergy, but it inherits the training difficulty that ACO documents for reinforcement-learning acquisition on 784 features. It also offers no way to tell when it will fail. On tasks drawn from its training prior, L2M may beat us in accuracy. The planted-synergy experiment below tests whether it degrades when the synergy order or structure falls outside that prior, while our $\gamma_r$ estimate predicts our own degradation.
Why not just run greedy over all pairs? That is exactly our ablation. At $d = 784$ there are about 307,000 pairs, each needing many nearest-neighbor draws per step, per instance. Distilled sensing theory predicts that concentrating draws on survivors lets distillation find strong blocks at much weaker gain signal than uniform scoring needs. If the ablation shows no gap, we drop the distillation claim.
Why not just use bandit-style successive halving instead of distilled sensing? It is essentially the same elimination idea, and we do not claim otherwise. What the sensing literature adds is the thresholding variant that needs no knowledge of the signal amplitude (Malloy) and the analysis of how weak a sparse signal can be and still be found. We will compare median-halving and threshold-based elimination directly.
Proposed Experiments
The decisive synthetic test uses XOR cubes with planted synergy of order 1, 2, and 3 at $d$ from 16 to 512. At $d \le 16$ exhaustive search gives the true optimum. There we check three predictions: one-step greedy collapses exactly when the empirical $\gamma_1$ is near zero, block greedy's ratio to the optimum tracks $1 - e^{-\gamma_r / r}$, and distillation's oracle-call savings over uniform block greedy grow with $d$.
The real benchmarks are MNIST pixel acquisition, UCI Gas and Grid, Open Bandit, and the MIMIC-IV tasks. On each we report accuracy or log-loss against features acquired, oracle calls and wall-clock per decision, and the estimated $\gamma_1$ and $\gamma_2$.
The negative check matters as much as the positive ones. On datasets where estimated $\gamma_1$ is already high, the escalation trigger should rarely fire and our method should cost about as much as plain greedy. If block search fires often there without gains, the dead-zone detector is miscalibrated.
References
- Maximizing the spread of influence through a social network
- Distilled sensing: selective sampling for sparse signal recovery
- Distilled Sensing: Adaptive Sampling for Sparse Detection and Estimation
- Sequential Analysis in High Dimensional Multiple Testing and Sparse Recovery
- Acquisition Conditioned Oracle for Nongreedy Active Feature Acquisition
- Learning-To-Measure: In-Context Active Feature Acquisition
- Info-Greedy sequential adaptive compressed sensing
- Compressive binary search
- Deep probabilistic subsampling for task-adaptive compressed sensing
- SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios
- Coresets for Data-efficient Training of Machine Learning Models
- Non-Monotone Adaptive Submodular Maximization