# Submodular Information Selection for Hypothesis Testing with Misclassification Penalties

arXiv: https://arxiv.org/abs/2405.10930 · HTML: https://mlsanity.com/paper/2405.10930/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 17 May 2024.

## Builds on (most cited first, 9 of 9)

- [Fast Convergence Rates for Distributed Non-Bayesian Learning](https://mlsanity.com/paper/1508.05161/) (2015)
- [Social Learning and Distributed Hypothesis Testing](https://mlsanity.com/paper/1410.4307/) (2014)
- [Randomized Greedy Sensor Selection: Leveraging Weak Submodularity](https://mlsanity.com/paper/1807.08627/) (2018)
- [A New Approach to Distributed Hypothesis Testing and Non-Bayesian Learning: Improved Learning Rate and Byzantine-Resilience](https://mlsanity.com/paper/1907.03588/) (2019)
- [Online Active Perception for Partially Observable Markov Decision Processes with Limited Budget](https://mlsanity.com/paper/1910.02130/) (2019)
- [Sparsity-Promoting Sensor Selection for Non-linear Measurement Models](https://mlsanity.com/paper/1310.5251/) (2013)
- [On the Complexity and Approximability of Optimal Sensor Selection and Attack for Kalman Filtering](https://mlsanity.com/paper/2003.11951/) (2020)
- [Near-Optimal Data Source Selection for Bayesian Learning](https://mlsanity.com/paper/2011.10712/) (2020)
- [Weakly Submodular Functions](https://mlsanity.com/paper/1401.6697/) (2014)

## Built on by (most cited first, 3 of 3)

- [All models are wrong, some are useful: Model Selection with Limited Labels](https://mlsanity.com/paper/2410.13609/) (2024)
- [Diagnose Before You Compress: Prediction-Independent Bottleneck Witness Refinement for LLM Serving Traces](https://mlsanity.com/paper/2608.00423/) (2026)
- [Robust Information Selection for Hypothesis Testing with Misclassification Penalties](https://mlsanity.com/paper/2502.14738/) (2025)

## Abstract (arXiv)

We consider the problem of selecting an optimal subset of information sources for a hypothesis testing/classification task where the goal is to identify the true state of the world from a finite set of hypotheses, based on finite observation samples from the sources. In order to characterize the learning performance, we propose a misclassification penalty framework, which enables nonuniform treatment of different misclassification errors. In a centralized Bayesian learning setting, we study two variants of the subset selection problem: (i) selecting a minimum cost information set to ensure that the maximum penalty of misclassifying the true hypothesis is below a desired bound and (ii) selecting an optimal information set under a limited budget to minimize the maximum penalty of misclassifying the true hypothesis. Under certain assumptions, we prove that the objective (or constraints) of these combinatorial optimization problems are weak (or approximate) submodular, and establish high-probability performance guarantees for greedy algorithms. Further, we propose an alternate metric for information set selection which is based on the total penalty of misclassification. We prove that this metric is submodular and establish near-optimal guarantees for the greedy algorithms for both the information set selection problems. Finally, we present numerical simulations to validate our theoretical results over several randomly generated instances.