Adaptive Measurement Allocation for Learning Kernelized SVMs Under Noisy Observations

Artur Miroszewski

cs.LGMay 21, 2026

Adaptive Measurement Allocation for Learning Kernelized SVMs Under Noisy Observations

Authors: Artur Miroszewski

Organizations: Φ-lab, European Space Agency (ESA/ESRIN), Frascati, Italy

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...

Explore similar work

May 14, 2026cs.LG

AQKA: Active Quantum Kernel Acquisition Under a Shot Budget

Estimating an

N \times N

quantum kernel from circuit fidelities requires

Θ(N^2 S)

measurement shots, the dominant bottleneck for deployment on near-term hardware. Existing budget-saving methods (Nyström-QKE, ShoFaR, kernel-target alignment) sub-sample \emph{which} entries to measure but allocate shots \emph{uniformly} within their chosen subset, ignoring how much each entry drives the downstream classifier. We close this gap with two contributions. \textbf{First, a complete regime decomposition} for shot-budgeted quantum kernel learning: a principled menu of when each allocator wins. Our method, \emph{AQKA}, dominates the budget-limited regime (

B \lesssim 16 n_{\mathrm{pairs}}

) on sparse-sensitivity KRR, with the gap \emph{growing} from

+8

+25

pts over uniform as

N

scales

225{\to}1000

and reaching

+26

32

pts on an \texttt{ibm_pittsburgh} (156-qubit Heron) hardware kernel; Nyström-QKE wins at saturating budgets on planted-sparse via low-rank reconstruction; ShoFaR is competitive only at extreme low budgets. \textbf{Second, a closed-form pair-level acquisition theory}:

s_{ij}^{\star} \propto |g_{ij}|\sqrt{K_{ij}(1-K_{ij})}

with explicit gradient

g_{ij}

for KRR (Lemma1, $|β_iα_j+β_jα_i|\sqrt{K_{ij}(1-K_{ij})}$ ) and SVM via the envelope theorem ( $|η_i^*η_j^*|\sqrt{K_{ij}(1-K_{ij})}$ ); a \emph{corrected} sparsity-aware Cauchy--Schwarz rate $ρ\le 2m/N$ matching empirics (vs.\ the naive $m^2/N^2$ ); an explicit-constant plug-in regret bound (Theorem2); and a tighter SVM ceiling

ρ^{\mathrm{SVM}} \le m_{\mathrm{sv}}^2/N^2

. We close with the first multi-seed live online adaptive shot allocation on quantum hardware:

+17.0 \pm 4.8

pts at

N{=}20

on \texttt{ibm_aachen} (

3.5σ

, 5 seeds), with the advantage holding at

N{=}30

at higher budget on \texttt{ibm_berlin} (

+14.0 \pm 8.5

pts, 5 seeds).

Jian Xu, Chao Li, Delu Zeng +2

Quantum Kernels Quantum Computing Token Budgets Sparsity

Ask PDF

Jun 27, 2026cs.LG

Active Quantum Kernel Acquisition for Gaussian Process Regression

Quantum kernel estimation on near-term hardware is shot-budgeted: every entry of the kernel Gram matrix is a Bernoulli expectation that must be sampled with a finite number of circuit executions. Recent work on quantum kernel classification has shown that allocating shots non-uniformly across kernel entries, weighted by their downstream task sensitivity, can reduce the shot budget required to reach a target accuracy. We extend this idea to Gaussian process (GP) regression, a setting whose downstream quantities (full-spectrum posterior variance, log-determinant, marginal likelihood) couple to kernel error more tightly than the sign-only outputs of classification. We derive three closed-form pair-level sensitivities predictive coupling

|α_iα_j|

, leave-one-out residual, and marginal-likelihood gradient and plug them into a Neyman-style minimum-variance allocation rule. To prevent catastrophic over-concentration when the warm-up sensitivity estimate is itself noisy, we add a high uniform coverage floor justified by a Frobenius lower bound on the missing-entry perturbation. On four UCI benchmarks and two synthetic RBF + Bernoulli controlled studies, the resulting allocator delivers

10

21\%

test-RMSE improvement over uniform allocation across the moderate-budget regime. The gain transfers (i) to genuine ZZ and Pauli-Z quantum kernels on quantum-natural data (

-13

15\%

at low budget,

p<0.05

paired) and (ii) to four downstream tasks (Bayesian quadrature, heteroscedastic regression, hyperparameter learning, multi-output Cokriging). On UCI features embedded into a ZZ kernel the gain disappears, consistent with the exponential-concentration regime where shot allocation has nothing to exploit.

Jian Xu, Artur Miroszewski, John Paisley +2

Quantum Kernels Gaussian Process Graphics Processing Unit Kernels Gibbs Measures Bayesian Quadrature Posterior+2

Ask PDF

Apr 20, 2026quant-ph

Benchmarking Quantum Kernel Support Vector Machines Against Classical Baselines on Tabular Data: A Rigorous Empirical Study with Hardware Validation

Quantum kernel methods have been proposed as a promising approach for leveraging near-term quantum computers for supervised learning, yet rigorous benchmarks against strong classical baselines remain scarce. We present a comprehensive empirical study of quantum kernel support vector machines (QSVMs) across nine binary classification datasets, four quantum feature maps, three classical kernels, and multiple noise models, totalling 970 experiments with strict nested cross-validation. Our analysis spans four phases: (i) statistical significance testing, revealing that none of 29 pairwise quantum-classical comparisons reach significance at

α= 0.05

; (ii) learning curve analysis over six training fractions, showing steeper quantum slopes on six of eight datasets that nonetheless fail to close the gap to the best classical baseline; (iii) hardware validation on IBM ibm_fez (Heron r2), demonstrating kernel fidelity

r \geq 0.976

across six experiments; and (iv) seed sensitivity analysis confirming reproducibility (mean CV 1.4%). A Kruskal-Wallis factorial analysis reveals that dataset choice dominates performance variance (

\varepsilon^2 = 0.73

), while kernel type accounts for only 9%. Spectral analysis offers a mechanistic explanation: current quantum feature maps produce eigenspectra that are either too flat or too concentrated, missing the intermediate profile of the best classical kernel, the radial basis function (RBF). Quantum kernel training (QKT) via kernel-target alignment yields the single competitive result -- balanced accuracy 0.968 on breast cancer -- but with ~2,000x computational overhead. Our findings provide actionable guidelines for quantum kernel research. The complete benchmark suite is publicly available to facilitate reproduction and extension.

Siavash Kakavand, Christoph Strohmeyer, Michael Schlotter

Quantum Kernels Hybrid Quantum Neural Networks Tabular Data

Ask PDF