Optimizing Kernel Discrepancies via Subset Selection

• URL: http://arxiv.org/abs/2511.02706v1
• Date: Tue, 04 Nov 2025 16:25:08 GMT
• Title: Optimizing Kernel Discrepancies via Subset Selection
• Authors: Deyao Chen, François Clément, Carola Doerr, Nathan Kirk,
• Abstract summary: 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.
• Score: 0.1259953341639576
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Kernel discrepancies are a powerful tool for analyzing worst-case errors in quasi-Monte Carlo (QMC) methods. Building on recent advances in optimizing such discrepancy measures, we extend the subset selection problem to the setting of kernel discrepancies, selecting an m-element subset from a large population of size $n \gg m$. We introduce a novel subset selection algorithm applicable to general kernel discrepancies to efficiently generate low-discrepancy samples from both the uniform distribution on the unit hypercube, the traditional setting of classical QMC, and from more general distributions $F$ with known density functions by employing the kernel Stein discrepancy. We also explore the relationship between the classical $L_2$ star discrepancy and its $L_\infty$ counterpart.

Related papers

• A Bayesian Approach to Low-Discrepancy Subset Selection [0.0]
  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.
  arXiv  Detail & Related papers  (2026-02-16T10:11:07Z)
• Analysis of Kernel Mirror Prox for Measure Optimization [4.6080589718744305]
  We study in a unified framework a class of functional saddle-point optimization problems, which we term the Mixed Functional Nash Equilibrium (MFNE) We model the saddle-point optimization dynamics as an interacting Fisher-Rao-RKHS gradient flow. We provide a unified convergence analysis of KMP in an infinite-dimensional setting for this class of MFNE problems.
  arXiv  Detail & Related papers  (2024-02-29T21:55:17Z)
• Variational Autoencoder Kernel Interpretation and Selection for Classification [59.30734371401315]
  This work proposed kernel selection approaches for probabilistic classifiers based on features produced by the convolutional encoder of a variational autoencoder. In the proposed implementation, each latent variable was sampled from the distribution associated with a single kernel of the last encoder's convolution layer, as an individual distribution was created for each kernel. choosing relevant features on the sampled latent variables makes it possible to perform kernel selection, filtering the uninformative features and kernels.
  arXiv  Detail & Related papers  (2022-09-10T17:22:53Z)
• Local Sample-weighted Multiple Kernel Clustering with Consensus Discriminative Graph [73.68184322526338]
  Multiple kernel clustering (MKC) is committed to achieving optimal information fusion from a set of base kernels. This paper proposes a novel local sample-weighted multiple kernel clustering model. Experimental results demonstrate that our LSWMKC possesses better local manifold representation and outperforms existing kernel or graph-based clustering algo-rithms.
  arXiv  Detail & Related papers  (2022-07-05T05:00:38Z)
• Feature subset selection for kernel SVM classification via mixed-integer optimization [0.7734726150561088]
  We study the mixed-integer optimization (MIO) approach to feature subset selection in nonlinear kernel support vector machines (SVMs) for binary classification. First proposed for linear regression in the 1970s, this approach has recently moved into the spotlight with advances in optimization algorithms and computer hardware. We propose a mixed-integer linear optimization (MILO) formulation based on the kernel-target alignment for feature subset selection, and this MILO problem can be solved to optimality using optimization software.
  arXiv  Detail & Related papers  (2022-05-28T04:01:40Z)
• Kernel Selection for Stein Variational Gradient Descent [19.16800190883095]
  We propose a combination of multiple kernels to approximate the optimal kernel instead of a single one. The proposed method not only gets rid of optimal kernel dependence but also maintains computational effectiveness.
  arXiv  Detail & Related papers  (2021-07-20T08:48:42Z)
• A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
  Kernel mean embeddings represent probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space. We show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense. We provide algorithms to optimize such distributions in the finite-sample setting.
  arXiv  Detail & Related papers  (2021-06-18T08:33:45Z)
• Taming Nonconvexity in Kernel Feature Selection---Favorable Properties of the Laplace Kernel [77.73399781313893]
  A challenge is to establish the objective function of kernel-based feature selection. The gradient-based algorithms available for non-global optimization are only able to guarantee convergence to local minima.
  arXiv  Detail & Related papers  (2021-06-17T11:05:48Z)
• Marginalising over Stationary Kernels with Bayesian Quadrature [36.456528055624766]
  Marginalising over families of Gaussian Process kernels produces flexible model classes with well-calibrated uncertainty estimates. We propose a Bayesian Quadrature scheme to make this marginalisation more efficient and thereby more practical.
  arXiv  Detail & Related papers  (2021-06-14T14:23:34Z)
• Kernel k-Means, By All Means: Algorithms and Strong Consistency [21.013169939337583]
  Kernel $k$ clustering is a powerful tool for unsupervised learning of non-linear data. In this paper, we generalize results leveraging a general family of means to combat sub-optimal local solutions. Our algorithm makes use of majorization-minimization (MM) to better solve this non-linear separation problem.
  arXiv  Detail & Related papers  (2020-11-12T16:07:18Z)
• Non-Convex SGD Learns Halfspaces with Adversarial Label Noise [50.659479930171585]
  We show the solution to the problem of learning surrogate learning homogeneous halfspaces in the distribution-specific model. In any convex distributions, we show that the misclassification error inherently leads to misclassification error of halfspace.
  arXiv  Detail & Related papers  (2020-06-11T18:55:59Z)
• SimpleMKKM: Simple Multiple Kernel K-means [49.500663154085586]
  We propose a simple yet effective multiple kernel clustering algorithm, termed simple multiple kernel k-means (SimpleMKKM) Our criterion is given by an intractable minimization-maximization problem in the kernel coefficient and clustering partition matrix. We theoretically analyze the performance of SimpleMKKM in terms of its clustering generalization error.
  arXiv  Detail & Related papers  (2020-05-11T10:06:40Z)

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.