Adaptive Measurement Allocation for Learning Kernelized SVMs Under Noisy Observations

• URL: http://arxiv.org/abs/2605.22275v1
• Date: Thu, 21 May 2026 10:19:23 GMT
• Title: Adaptive Measurement Allocation for Learning Kernelized SVMs Under Noisy Observations
• Abstract summary: Kernel methods are typically formulated under the assumption of exact, noise-free access to the Gram matrix.<n>In emerging settings such as quantum machine learning, each kernel entry must be inferred from noisy observations.<n>We introduce an adaptive measurement-allocation strategy for learning kernelized Support Vector Machines.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Kernel methods are typically formulated under the assumption of exact, noise-free access to the Gram matrix. However, in emerging settings such as quantum machine learning, each kernel entry must be inferred from noisy observations, and its accuracy depends on how a limited measurement budget is allocated. Despite this, existing approaches overwhelmingly rely on uniform allocation, which equalizes estimator variance but ignores the highly non-uniform dependence of kernelized classifiers on the Gram matrix. In this work, we introduce an adaptive measurement-allocation strategy for learning kernelized Support Vector Machines (SVMs) from noisy Bernoulli observations. Our approach combines two complementary principles: (i) geometric sensitivity, capturing how perturbations of individual kernel entries affect the classifier margin, and (ii) active-set instability, quantifying the probability of discrete changes in support-vector membership induced by measurement noise. These signals define a task-aware allocation scheme that concentrates measurements on the most decision-critical regions of the kernel matrix. We provide a theoretical analysis showing that the benefit of adaptive allocation is governed by the heterogeneity of the induced kernel importance structure, leading to distinct regimes in which adaptive or uniform strategies are preferable. Empirical evaluations on synthetic datasets demonstrate that adaptive allocation significantly improves support-vector recovery, margin estimation, and decision-function accuracy under fixed measurement budgets. A dual-coefficient stability criterion further enables early stopping, achieving near-optimal performance while using only a fraction of the measurement cost. Additional experiments on quantum kernels derived from real-world data reveal a regime-dependent behavior aligned with known phenomena such as kernel concentration. Together...

Related papers

• Variational Rectification Inference for Learning with Noisy Labels [74.85528327499662]
  We propose variational rectification inference (VRI) to formulate the adaptive rectification for loss functions.<n>VRI is constructed as a hierarchical Bayes by treating the rectifying vector as a latent variable.<n>By introducing the variational term in VRI, the conditional posterior is estimated accurately and avoids collapsing to a Dirac delta function.
  arXiv  Detail & Related papers  (2026-03-18T01:25:08Z)
• Deterministic Coreset Construction via Adaptive Sensitivity Trimming [0.2864713389096699]
  We develop a framework for deterministic coreset construction in empirical risk minimization.<n>Our central contribution is the Adaptive Deterministic Uniform-Weight Trimming (ADUWT) algorithm.<n>We conclude with open problems on instance-optimal oracles, deterministic streaming, and fairness-constrained ERM.
  arXiv  Detail & Related papers  (2025-08-25T17:19:13Z)
• A Sparse Bayesian Learning Algorithm for Estimation of Interaction Kernels in Motsch-Tadmor Model [0.9821874476902972]
  We investigate the data-driven identification of asymmetric interaction kernels in the Motsch-Tadmor model.<n>We propose a variational framework that reformulates kernel identification using the implicit form of the governing equations.<n>We develop a sparse Bayesian learning algorithm that incorporates informative priors for regularization, quantifies uncertainty, and enables principled model selection.
  arXiv  Detail & Related papers  (2025-05-11T17:43:32Z)
• Towards Initialization-Agnostic Clustering with Iterative Adaptive Resonance Theory [8.312275539092466]
  Iterative Refinement Adaptive Resonance Theory (IR-ART) integrates three key phases into a unified iterative framework.<n> IR-ART improves tolerance to suboptimal vigilance parameter values while preserving the parameter simplicity of Fuzzy ART.<n>Case studies visually confirm the algorithm's self-optimization capability through iterative refinement.
  arXiv  Detail & Related papers  (2025-05-07T14:12:39Z)
• Synergistic eigenanalysis of covariance and Hessian matrices for enhanced binary classification [72.77513633290056]
  We present a novel approach that combines the eigenanalysis of a covariance matrix evaluated on a training set with a Hessian matrix evaluated on a deep learning model. Our method captures intricate patterns and relationships, enhancing classification performance.
  arXiv  Detail & Related papers  (2024-02-14T16:10:42Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Reconstructing Kernel-based Machine Learning Force Fields with Super-linear Convergence [0.18416014644193063]
  We consider the broad class of Nystr"om-type methods to construct preconditioners. All considered methods aim to identify a representative subset of inducing ( Kernel) columns to approximate the dominant kernel spectrum.
  arXiv  Detail & Related papers  (2022-12-24T13:45:50Z)
• Nonparametric learning of kernels in nonlocal operators [6.314604944530131]
  We provide a rigorous identifiability analysis and convergence study for the learning of kernels in nonlocal operators. We propose a nonparametric regression algorithm with a novel data adaptive RKHS Tikhonov regularization method based on the function space of identifiability.
  arXiv  Detail & Related papers  (2022-05-23T02:47:55Z)
• Meta-Learning Hypothesis Spaces for Sequential Decision-making [79.73213540203389]
  We propose to meta-learn a kernel from offline data (Meta-KeL) Under mild conditions, we guarantee that our estimated RKHS yields valid confidence sets. We also empirically evaluate the effectiveness of our approach on a Bayesian optimization task.
  arXiv  Detail & Related papers  (2022-02-01T17:46:51Z)
• Estimating Average Treatment Effects with Support Vector Machines [77.34726150561087]
  Support vector machine (SVM) is one of the most popular classification algorithms in the machine learning literature. We adapt SVM as a kernel-based weighting procedure that minimizes the maximum mean discrepancy between the treatment and control groups. We characterize the bias of causal effect estimation arising from this trade-off, connecting the proposed SVM procedure to the existing kernel balancing methods.
  arXiv  Detail & Related papers  (2021-02-23T20:22:56Z)
• 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)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)

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.