A Bayesian Approach to Low-Discrepancy Subset Selection

• URL: http://arxiv.org/abs/2602.14607v1
• Date: Mon, 16 Feb 2026 10:11:07 GMT
• Title: A Bayesian Approach to Low-Discrepancy Subset Selection
• Authors: Nathan Kirk,
• Abstract summary: Low-discrepancy designs play a central role in quasi-Monte Carlo methods and are increasingly influential in other domains such as machine learning, robotics and computer graphics.<n>In recent years, one such low-discrepancy construction method called subset selection has received a lot of attention.<n>We establish, for the first time, that the subset selection problem with respect to kernel discrepancies is also NP-hard.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Low-discrepancy designs play a central role in quasi-Monte Carlo methods and are increasingly influential in other domains such as machine learning, robotics and computer graphics, to name a few. In recent years, one such low-discrepancy construction method called subset selection has received a lot of attention. Given a large population, one optimally selects a small low-discrepancy subset with respect to a discrepancy-based objective. Versions of this problem are known to be NP-hard. In this text, we establish, for the first time, that the subset selection problem with respect to kernel discrepancies is also NP-hard. Motivated by this intractability, we propose a Bayesian Optimization procedure for the subset selection problem utilizing the recent notion of deep embedding kernels. We demonstrate the performance of the BO algorithm to minimize discrepancy measures and note that the framework is broadly applicable any design criteria.

Related papers

• Optimizing Kernel Discrepancies via Subset Selection [0.1259953341639576]
  Kernel discrepancies are a powerful tool for analyzing worst-case errors in quasi-Monte Carlo (QMC) methods.<n>We introduce a novel subset selection algorithm applicable to general kernel discrepancies.
  arXiv  Detail & Related papers  (2025-11-04T16:25:08Z)
• Policy Testing in Markov Decision Processes [48.642181362172906]
  We study the policy testing problem in discounted decision processes (MDP) under the fixed-confidence setting.<n>The goal is to determine whether the value of a given policy exceeds a numerical threshold.
  arXiv  Detail & Related papers  (2025-05-21T10:13:54Z)
• Pareto Optimization with Robust Evaluation for Noisy Subset Selection [34.83487850400559]
  Subset selection is a fundamental problem in optimization, which has a wide range of applications such as influence and sparse regression.<n>Previous algorithms, including the greedy algorithm and evolutionary evolutionary POSS, either struggle in noisy environments or consume excessive computational resources.<n>We propose a novel approach based on Pareto Optimization with Robust Evaluation for noisy subset selection (PORE), which maximizes a robust evaluation function and minimizes the subset size simultaneously.
  arXiv  Detail & Related papers  (2025-01-12T14:04:20Z)
• Near-Optimal Algorithm for Non-Stationary Kernelized Bandits [6.379833644595456]
  We study a non-stationary kernelized bandit (KB) problem, also called time-varying Bayesian optimization. We show the first algorithm-independent regret lower bound for non-stationary KB with squared exponential and Mat'ern kernels. We propose a novel near-optimal algorithm called restarting phased elimination with random permutation.
  arXiv  Detail & Related papers  (2024-10-21T14:28:26Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Message-Passing Monte Carlo: Generating low-discrepancy point sets via Graph Neural Networks [64.39488944424095]
  We present the first machine learning approach to generate low-discrepancy point sets named Message-Passing Monte Carlo points. MPMC points are empirically shown to be either optimal or near-optimal with respect to the discrepancy for low dimension and small number of points.
  arXiv  Detail & Related papers  (2024-05-23T21:17:20Z)
• On Distributed Larger-Than-Memory Subset Selection With Pairwise Submodular Functions [31.334053253182795]
  We propose a novel distributed bounding algorithm with provable approximation guarantees.<n>We find high quality subsets on CIFAR-100 and ImageNet with marginal or no loss in quality compared to centralized methods.
  arXiv  Detail & Related papers  (2024-02-26T09:38:39Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Attention-oriented Brain Storm Optimization for Multimodal Optimization Problems [24.38312890501329]
  This paper presents an Attention-oriented Brain Storm Optimization (ABSO) method that introduces the attention mechanism into a relatively new swarm intelligence algorithm. Rather than converge to a single global optimum, the proposed method can guide the search procedure to converge to multiple "salient" solutions.
  arXiv  Detail & Related papers  (2021-05-27T12:47:57Z)
• Optimal quantisation of probability measures using maximum mean discrepancy [10.29438865750845]
  Several researchers have proposed minimisation of maximum mean discrepancy (MMD) as a method to quantise probability measures. We consider sequential algorithms that greedily minimise MMD over a discrete candidate set. We investigate a variant that applies this technique to a mini-batch of the candidate set at each iteration.
  arXiv  Detail & Related papers  (2020-10-14T13:09:48Z)
• 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)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  Simple algorithms have been shown to lead to good empirical results in many contexts. Several works have pursued rigorous analytical justification for studying non optimization problems. A key insight in these analyses is that perturbations play a critical role in allowing local descent algorithms.
  arXiv  Detail & Related papers  (2020-03-31T16:54:22Z)

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.