Research map / Learning theory and algorithms / Prediction and decision losses

Performance Bounds for Active Binary Testing with Information Maximization

ICML 2024 · Learning theory and algorithms › Prediction and decision losses · approach: Adaptive testing and experiments

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives non-vacuous performance bounds for the greedy InfoMax test-selection heuristic under a δ-unpredictability assumption, for oracle tests and for tests corrupted by a binary symmetric channel.

Problem

Active binary testing to predict a random variable Y: the greedy InfoMax strategy is widely used, but existing worst-case guarantees on its expected number of tests are vacuous relative to its empirical efficiency, especially with noisy tests.

Approach

Assume at each greedy iteration some binary test has success probability within δ of one-half (δ-unpredictability). Under this assumption, the expected number of tests of InfoMax is at most H(Y)/h(1/2+δ) for oracle tests and H(Y)/(h(1/2+δ)-h(α)) under a BSC noise model with crossover α, a bound shown tight for oracle tests.

Key results

• For oracle tests, the bound H(Y)/h(1/2+δ) is tight: an explicit construction makes greedy achieve it exactly.
• On 20Q with birds (δ=0.22), InfoMax needs 7.70 tests versus bound 8.93, while the Loveland bound gives 17.44 and the Dasgupta bound 161.86 (H(Y)=7.64).
• On 20Q with animals (δ=0.17), InfoMax needs 5.73 tests versus bound 6.17, compared with 12.69 for the Loveland bound and 88.31 for the Dasgupta bound.

Measured effects reported in the paper

Surprising findings

• The empirical δ values on CUB and AwA2 are small enough (0.22 and 0.17) that the greedy test selection is near-bisecting even though the tests are coarse and incomplete.

Limitations

• The δ value is assumed known, but there is no practical way to find δ for a given test set in advance.
• The BSC noise model assumes i.i.d. noise independent across tests, which may not hold in practice.
• The noisy bound does not explicitly depend on the confidence level γ.

Experimental setup

Datasets: CUB-200-2011 AwA2

Benchmarks: CUB-200-2011 20Q with birds AwA2 20Q with animals

Metrics: average number of tests ratio of bound to InfoMax performance delta-unpredictability empirical distribution

Baselines: Loveland (1985) bound Dasgupta (2004) bound Kosaraju et al. (1999) bound

Builds on: Generalized Binary Search (Dasgupta, 2004) Loveland (1985) delta-unpredictable analysis Kosaraju et al. (1999) Jedynak et al. (2012)

Closest papers by meaning

• Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.83)
• Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.83)
• Strategic A/B testing via Maximum Probability-driven Two-armed Bandit (ICML 2025 · similarity 0.83)
• Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence (ICML 2025 · similarity 0.82)
• Peeking with PEAK: Sequential, Nonparametric Composite Hypothesis Tests for Means of Multiple Data Streams (ICML 2024 · similarity 0.82)
• A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization (ICML 2025 · similarity 0.82)