Optimizing Input Data Collection for Ranking and Selection

• URL: http://arxiv.org/abs/2502.16659v1
• Date: Sun, 23 Feb 2025 17:33:43 GMT
• Title: Optimizing Input Data Collection for Ranking and Selection
• Authors: Eunhye Song, Taeho Kim,
• Abstract summary: We design a sequential sampling algorithm that collects input and simulation data given a budget.<n>We show that MPB's posterior probability of optimality converges to one at an exponential rate as the sampling budget increases.<n>We extend OSAR by adopting the kernel ridge regression to improve the simulation output mean prediction.
• Score: 2.3708672042234213
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a ranking and selection (R&S) problem when all solutions share common parametric Bayesian input models updated with the data collected from multiple independent data-generating sources. Our objective is to identify the best system by designing a sequential sampling algorithm that collects input and simulation data given a budget. We adopt the most probable best (MPB) as the estimator of the optimum and show that its posterior probability of optimality converges to one at an exponential rate as the sampling budget increases. Assuming that the input parameters belong to a finite set, we characterize the $\epsilon$-optimal static sampling ratios for input and simulation data that maximize the convergence rate. Using these ratios as guidance, we propose the optimal sampling algorithm for R&S (OSAR) that achieves the $\epsilon$-optimal ratios almost surely in the limit. We further extend OSAR by adopting the kernel ridge regression to improve the simulation output mean prediction. This not only improves OSAR's finite-sample performance, but also lets us tackle the case where the input parameters lie in a continuous space with a strong consistency guarantee for finding the optimum. We numerically demonstrate that OSAR outperforms a state-of-the-art competitor.

Related papers

• Parallel simulation for sampling under isoperimetry and score-based diffusion models [56.39904484784127]
  As data size grows, reducing the iteration cost becomes an important goal.<n>Inspired by the success of the parallel simulation of the initial value problem in scientific computation, we propose parallel Picard methods for sampling tasks.<n>Our work highlights the potential advantages of simulation methods in scientific computation for dynamics-based sampling and diffusion models.
  arXiv  Detail & Related papers  (2024-12-10T11:50:46Z)
• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
  We propose the Observation-Aware Spectral (OAS) estimation technique, which enables the POMDP parameters to be learned from samples collected using a belief-based policy. We show the consistency of the OAS procedure, and we prove a regret guarantee of order $mathcalO(sqrtT log(T)$ for the proposed OAS-UCRL algorithm.
  arXiv  Detail & Related papers  (2024-10-02T08:46:34Z)
• Adaptive Selection of Sampling-Reconstruction in Fourier Compressed Sensing [13.775902519100075]
  Compressed sensing (CS) has emerged to overcome the inefficiency of Nyquist sampling. Deep learning-based reconstruction has been a promising alternative to optimization-based reconstruction.
  arXiv  Detail & Related papers  (2024-09-18T06:51:29Z)
• Bayesian Frequency Estimation Under Local Differential Privacy With an Adaptive Randomized Response Mechanism [0.4604003661048266]
  We propose AdOBEst-LDP, a new algorithm for adaptive, online Bayesian estimation of categorical distributions under local differential privacy.<n>By adapting the subset selection process to the past privatized data via Bayesian estimation, the algorithm improves the utility of future privatized data.
  arXiv  Detail & Related papers  (2024-05-11T13:59:52Z)
• Stochastic optimization with arbitrary recurrent data sampling [2.1485350418225244]
  Most commonly used data sampling algorithms are under mild assumptions. We show that for a particular class of recurrent optimization algorithms, we do not need any other property. We show that convergence can be accelerated by selecting sampling algorithms that cover the data set.
  arXiv  Detail & Related papers  (2024-01-15T14:04:50Z)
• Data-Driven Optimization of Directed Information over Discrete Alphabets [15.372626012233736]
  Directed information (DI) is a fundamental measure for the study and analysis of sequential analytic models. We propose a novel estimation-optimization framework for DI over discrete input spaces.
  arXiv  Detail & Related papers  (2023-01-02T12:25:40Z)
• Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
  Annealed Importance Sampling (AIS) is a popular algorithm used to estimates the intractable marginal likelihood of deep generative models. We present a parameteric AIS process with flexible intermediary distributions and optimize the bridging distributions to use fewer number of steps for sampling. We assess the performance of our optimized AIS for marginal likelihood estimation of deep generative models and compare it to other estimators.
  arXiv  Detail & Related papers  (2022-09-27T07:58:25Z)
• Selection of the Most Probable Best [2.1095005405219815]
  We consider an expected-value ranking and selection (R&S) problem where all k solutions' simulation outputs depend on a common parameter whose uncertainty can be modeled by a distribution. We define the most probable best (MPB) to be the solution that has the largest probability of being optimal with respect to the distribution. We devise a series of algorithms that replace the unknown means in the optimality conditions with their estimates and prove the algorithms' sampling ratios achieve the conditions as the simulation budget increases.
  arXiv  Detail & Related papers  (2022-07-15T15:27:27Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Bayesian Optimisation vs. Input Uncertainty Reduction [1.0497128347190048]
  We consider the trade-off between simulation and real data collection in order to find the optimal solution of the simulator with the true inputs. We propose a novel unified simulation optimisation procedure called Bayesian Information Collection and optimisation.
  arXiv  Detail & Related papers  (2020-05-31T23:42:22Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)

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.