An Asymptotically Optimal Algorithm for the Convex Hull Membership Problem
We study the convex hull membership (CHM) problem in the pure exploration setting where one aims to efficiently and accurately determine if a given point lies in the convex hull of means of a finite set of distributions. We give a complete characterization of the sample complexity of the CHM problem in the one-dimensional case. We present the first asymptotically optimal algorithm called Thompson-CHM, whose modular design consists of a stopping rule and a sampling rule. In addition, we extend the algorithm to settings that generalize several important problems in the multi-armed bandit literature. Furthermore, we discuss the extension of Thompson-CHM to higher dimensions. Finally, we provide numerical experiments to demonstrate the empirical behavior of the algorithm matches our theoretical results for realistic time horizons.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Beyond Bounding-Box: Convex-Hull Feature Adaptation for Oriented and Densely Packed Object Detection
Detecting oriented and densely packed objects remains challenging for spatial feature aliasing caused by the intersection of reception fields between objects. In this paper, we propose a convex-hull feature adaptatio…
object-detectionObject DetectionObject Detection In Aerial ImagesA Sketching Method for Finding the Closest Point on a Convex Hull
We develop a sketching algorithm to find the point on the convex hull of a dataset, closest to a query point outside it. Studying the convex hull of datasets can provide useful information about their geometric structure…
Multiobjective Optimization of Classifiers by Means of 3-D Convex Hull Based Evolutionary Algorithm
Finding a good classifier is a multiobjective optimization problem with different error rates and the costs to be minimized. The receiver operating characteristic is widely used in the machine learning community to analy…
Binary ClassificationClassificationEvolutionary Algorithmsfeature selection+3Convex Hull Approximation of Nearly Optimal Lasso Solutions
In an ordinary feature selection procedure, a set of important features is obtained by solving an optimization problem such as the Lasso regression problem, and we expect that the obtained features explain the data well.…
Diversityfeature selectionAn Extended Integral Unit Commitment Formulation and an Iterative Algorithm for Convex Hull Pricing
To increase market transparency, independent system operators (ISOs) have been working on minimizing uplift payments based on convex hull pricing theorems. However, the large-scale complex systems for ISOs bring computat…
Computational Efficiency