Submodular Information Selection for Hypothesis Testing with Misclassification Penalties

• URL: http://arxiv.org/abs/2405.10930v3
• Date: Fri, 28 Jun 2024 03:51:23 GMT
• Title: Submodular Information Selection for Hypothesis Testing with Misclassification Penalties
• Authors: Jayanth Bhargav, Mahsa Ghasemi, Shreyas Sundaram,
• Abstract summary: We study the problem of selecting an optimal subset of information sources for a hypothesis testing/classification task. We propose a misclassification penalty framework, which enables nonuniform treatment of different misclassification errors. We prove that this metric is submodular and establish near-optimal guarantees for the greedy algorithms for both the information set selection problems.
• Score: 3.3444620077119436
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
  We first construct a max-margin optimization-based model to model potentially non-monotonic preferences. We devise information amount measurement methods and question selection strategies to pinpoint the most informative alternative in each iteration. Two incremental preference elicitation-based algorithms are developed to learn potentially non-monotonic preferences.
  arXiv  Detail & Related papers  (2024-09-04T14:36:20Z)
• Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
  We aim to learn decision policies that optimize an unbiased offline estimate of an online reward metric. We propose a single framework built on their equivalence in learning scenarios. Our framework enables us to characterize the variance-optimal unbiased estimator and provide a closed-form solution for it.
  arXiv  Detail & Related papers  (2024-05-09T12:52:22Z)
• Non-Convex Robust Hypothesis Testing using Sinkhorn Uncertainty Sets [18.46110328123008]
  We present a new framework to address the non-robust hypothesis testing problem. The goal is to seek the optimal detector that minimizes the maximum numerical risk.
  arXiv  Detail & Related papers  (2024-03-21T20:29:43Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Optimize-via-Predict: Realizing out-of-sample optimality in data-driven optimization [0.0]
  We examine a formulation for data-driven optimization wherein the decision-maker is not privy to the true distribution. We define a prescriptive solution as a decisionvendor rule mapping such a data set to decisions. We present an optimization problem that would solve for such an out-of-sample optimal solution, and does so efficiently by a combination of sampling and bisection search algorithms.
  arXiv  Detail & Related papers  (2023-09-20T08:48:50Z)
• Bilevel Optimization for Feature Selection in the Data-Driven Newsvendor Problem [8.281391209717105]
  We study the feature-based news vendor problem, in which a decision-maker has access to historical data. In this setting, we investigate feature selection, aiming to derive sparse, explainable models with improved out-of-sample performance. We present a mixed integer linear program reformulation for the bilevel program, which can be solved to optimality with standard optimization solvers.
  arXiv  Detail & Related papers  (2022-09-12T08:52:26Z)
• Bi-objective Ranking and Selection Using Stochastic Kriging [0.0]
  We consider bi-objective ranking and selection problems in which the two objective outcomes have been observed with uncertainty. We propose a novel Bayesian bi-objective ranking and selection method that sequentially allocates extra samples to competitive solutions. Experimental results show that the proposed method outperforms the standard allocation method, as well as a well-known state-of-the-art algorithm.
  arXiv  Detail & Related papers  (2022-09-05T23:51:07Z)
• Bounding Counterfactuals under Selection Bias [60.55840896782637]
  We propose a first algorithm to address both identifiable and unidentifiable queries. We prove that, in spite of the missingness induced by the selection bias, the likelihood of the available data is unimodal.
  arXiv  Detail & Related papers  (2022-07-26T10:33:10Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  We study the fundamental problem of selecting optimal features for model construction. This problem is computationally challenging on large datasets, even with the use of greedy algorithm variants. We extend the adaptive query model, recently proposed for the greedy forward selection for submodular functions, to the faster paradigm of Orthogonal Matching Pursuit for non-submodular functions. The proposed algorithm achieves exponentially fast parallel run time in the adaptive query model, scaling much better than prior work.
  arXiv  Detail & Related papers  (2022-02-28T12:26:47Z)
• Near Instance Optimal Model Selection for Pure Exploration Linear Bandits [20.67688737534517]
  We study the model selection problem in the pure exploration linear bandit setting. Our goal is to automatically adapt to the instance-dependent complexity measure of the smallest hypothesis class. Our algorithms define a new optimization problem based on experimental design.
  arXiv  Detail & Related papers  (2021-09-10T22:56:58Z)
• Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
  Partial-label learning (PLL) is a typical weakly supervised learning problem, where each training instance is equipped with a set of candidate labels among which only one is the true label. Most existing methods elaborately designed as constrained optimizations that must be solved in specific manners, making their computational complexity a bottleneck for scaling up to big data. This paper proposes a novel framework of classifier with flexibility on the model and optimization algorithm.
  arXiv  Detail & Related papers  (2020-02-19T08:35:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.