Fat Shattering, Joint Measurability, and PAC Learnability of POVM Hypothesis Classes

• URL: http://arxiv.org/abs/2308.12304v1
• Date: Mon, 21 Aug 2023 18:38:24 GMT
• Title: Fat Shattering, Joint Measurability, and PAC Learnability of POVM Hypothesis Classes
• Abstract summary: We characterize learnability for quantum measurement classes by establishing matching necessary and sufficient conditions for their PAC learnability. We show that VC dimension generalization upper bounds in previous work are frequently infinite, even for finite-dimensional POVM classes. We show that every measurement class defined on a finite-dimensional Hilbert space is PAC learnable.
• Score: 8.594140167290098
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We characterize learnability for quantum measurement classes by establishing matching necessary and sufficient conditions for their PAC learnability, along with corresponding sample complexity bounds, in the setting where the learner is given access only to prepared quantum states. We first probe the results from previous works on this setting. We show that the empirical risk defined in previous works and matching the definition in the classical theory fails to satisfy the uniform convergence property enjoyed in the classical setting for some learnable classes. Moreover, we show that VC dimension generalization upper bounds in previous work are frequently infinite, even for finite-dimensional POVM classes. To surmount the failure of the standard ERM to satisfy uniform convergence, we define a new learning rule -- denoised ERM. We show this to be a universal learning rule for POVM and probabilistically observed concept classes, and the condition for it to satisfy uniform convergence is finite fat shattering dimension of the class. We give quantitative sample complexity upper and lower bounds for learnability in terms of finite fat-shattering dimension and a notion of approximate finite partitionability into approximately jointly measurable subsets, which allow for sample reuse. We then show that finite fat shattering dimension implies finite coverability by approximately jointly measurable subsets, leading to our matching conditions. We also show that every measurement class defined on a finite-dimensional Hilbert space is PAC learnable. We illustrate our results on several example POVM classes.

Related papers

• A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC [0.0]
  The fundamental theorem of statistical learning states that, under suitable measurability assumptions, finite Vapnik--Chervonenkis (VC) dimension guarantees that every proper consistent learning rule is probably approximately correct (PAC)<n>We show, with no need of extra set-theoretical assumptions, that the additional regularity assumption in the fundamental theorem cannot in general be omitted.
  arXiv  Detail & Related papers  (2026-08-31T04:56:40Z)
• Entanglement Quantification via Symmetric Extensions: A Resource Theory Hierarchy [3.662037602213926]
  We introduce a hierarchy of entanglement measures Ek based on k-symmetric PPT extensions.<n>Each Ek, defined via a minimal eigenvalue shift, is faithful, convex, and monotone under free operations.<n>The hierarchy strictly refines PPT-robustness at k = 1, detects bound entanglement at k = 2, and converges exactly to the separability measure as k -> infinity.
  arXiv  Detail & Related papers  (2026-07-18T20:39:35Z)
• Null Measurability at the Symmetrization Interface in VC Learning [0.15229257192293197]
  Recent revisiting of measurability in the fundamental theorem of statistical learning imposes Borel measurability of ghost-gap suprema.<n>We show that, at the one-sided ghost-gap interface actually used by the standard symmetrization proof, this requirement is stronger than necessary.<n>Results weaken the measurability hypothesis needed by the symmetrization route from finite VC to PAC learnability.
  arXiv  Detail & Related papers  (2026-04-27T22:10:34Z)
• Central Limit Theorems for Outcome Records in Disordered Quantum Trajectories [0.0]
  We prove CLT for finite pattern counts in the measurement record of discrete-time quantum trajectories generated by repeated measurements in a disordered environment.<n>We provide criteria and verify the assumptions across a broad family of examples, including disordered walk-type models generated by finite group actions.
  arXiv  Detail & Related papers  (2026-03-30T18:17:02Z)
• Learning Conditional Averages [52.361762722359366]
  We introduce the problem of learning conditional averages in the PAC framework.<n>Instead of learning the target concept itself, the goal is to predict, for each instance, the average label over its neighborhood.<n>More generally, it extends PAC learning to a setting that captures learning tasks arising in several domains.
  arXiv  Detail & Related papers  (2026-02-12T13:20:29Z)
• Robust Online Learning [0.0]
  We study the problem of learning robust classifiers where the classifier will receive a perturbed input.<n>We consider both the realizable and learnability of hypothesis classes.<n>We show it controls the mistake bounds in the realizable setting and the regret bounds in the agnostic setting.
  arXiv  Detail & Related papers  (2026-02-06T15:30:52Z)
• Partial Feedback Online Learning [88.27143767009376]
  We study a new learning protocol, termed partial-feedback online learning.<n>Each instance admits a set of acceptable labels, but the learner observes only one acceptable label per round.
  arXiv  Detail & Related papers  (2026-01-29T09:39:11Z)
• On the Fundamental Limits of LLMs at Scale [15.459708840379975]
  Large Language Models (LLMs) have benefited enormously from scaling, yet these gains are bounded by five fundamental limitations.<n>This work presents a unified, proof-informed framework that formalizes the innate theoretical ceilings of LLM scaling.<n>We show how likelihood-based training favors pattern completion over inference, how retrieval under token limits suffers from semantic drift and coupling noise, and how multimodal scaling inherits shallow cross-modal alignment.
  arXiv  Detail & Related papers  (2025-11-17T01:55:33Z)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  We show that multiclass PAC sample complexity is governed by two distinct dimensions.<n>Unlike binary or online classification, multiclass learning inherently involves two structural parameters.<n>A key ingredient is a novel online procedure based on a self-adaptive multiplicative-weights algorithm performing a label-space reduction.
  arXiv  Detail & Related papers  (2025-11-16T15:47:47Z)
• Certified Approximate Reachability (CARe): Formal Error Bounds on Deep Learning of Reachable Sets [45.67587657709892]
  We introduce an epsilon-approximate Hamilton-Jacobi Partial Differential Equation (HJ-PDE), which establishes a relationship between training loss and accuracy of the true reachable set. To the best of our knowledge, Certified Approximate Reachability (CARe) is the first approach to provide soundness guarantees on learned reachable sets of continuous dynamical systems.
  arXiv  Detail & Related papers  (2025-03-31T10:02:57Z)
• On consistent estimation of dimension values [45.52331418900137]
  The problem of estimating the dimension of a compact subset S of the Euclidean space is considered. The emphasis is put on consistency results in the statistical sense.
  arXiv  Detail & Related papers  (2024-12-18T14:40:37Z)
• Classification of joint quantum measurements based on entanglement cost of localization [42.72938925647165]
  We propose a systematic classification of joint measurements based on entanglement cost. We show how to numerically explore higher levels and construct generalizations to higher dimensions and multipartite settings.
  arXiv  Detail & Related papers  (2024-08-01T18:00:01Z)
• Leveraging PAC-Bayes Theory and Gibbs Distributions for Generalization Bounds with Complexity Measures [14.408127155170774]
  We leverage the framework of disintegrated PAC-Bayes bounds to derive a general generalization bound instantiable with arbitrary complexity measures. Our bound stands in probability jointly over the hypothesis and the learning sample, which allows the complexity to be adapted to the generalization gap.
  arXiv  Detail & Related papers  (2024-02-19T10:15:11Z)
• Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
  We aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. We first introduce a minimax instance optimal learner for realizable regression and propose a novel dimension that both qualitatively and quantitatively characterizes which classes of real-valued predictors are learnable. In the context of online learning we provide a dimension that characterizes the minimax optimal instance optimal cumulative loss up to a constant factor and design an optimal online learner for realizable regression.
  arXiv  Detail & Related papers  (2023-07-07T21:39:25Z)
• Integral Probability Metrics PAC-Bayes Bounds [22.534592918803813]
  We present a PAC-Bayes-style generalization bound which enables the replacement of the KL-divergence with a variety of Integral Probability Metrics (IPM) A notable feature of the obtained bounds is that they naturally interpolate between classical uniform convergence bounds in the worst case.
  arXiv  Detail & Related papers  (2022-07-01T18:22:44Z)
• On Leave-One-Out Conditional Mutual Information For Generalization [122.2734338600665]
  We derive information theoretic generalization bounds for supervised learning algorithms based on a new measure of leave-one-out conditional mutual information (loo-CMI) Contrary to other CMI bounds, our loo-CMI bounds can be computed easily and can be interpreted in connection to other notions such as classical leave-one-out cross-validation. We empirically validate the quality of the bound by evaluating its predicted generalization gap in scenarios for deep learning.
  arXiv  Detail & Related papers  (2022-07-01T17:58:29Z)
• A PAC-Bayesian Analysis of Distance-Based Classifiers: Why Nearest-Neighbour works! [12.317405551932195]
  PAC-Bayesian bounds for the generalisation error of the K-nearest-neighbour classifier (K-NN) We establish a relation between prior measures over the coefficients in the kernel expansion and the induced measure on the weight vectors in kernel space.
  arXiv  Detail & Related papers  (2021-09-28T17:35:57Z)
• Entanglement detection in quantum many-body systems using entropic uncertainty relations [0.0]
  We study experimentally accessible lower bounds on entanglement measures based on entropic uncertainty relations. We derive an improved entanglement bound for bipartite systems, which requires measuring joint probability distributions in only two different measurement settings per subsystem.
  arXiv  Detail & Related papers  (2021-01-21T20:50:11Z)
• The Variational Method of Moments [65.91730154730905]
  conditional moment problem is a powerful formulation for describing structural causal parameters in terms of observables. Motivated by a variational minimax reformulation of OWGMM, we define a very general class of estimators for the conditional moment problem. We provide algorithms for valid statistical inference based on the same kind of variational reformulations.
  arXiv  Detail & Related papers  (2020-12-17T07:21:06Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  We propose the amortized conditional normalized maximum likelihood (ACNML) method as a scalable general-purpose approach for uncertainty estimation. Our algorithm builds on the conditional normalized maximum likelihood (CNML) coding scheme, which has minimax optimal properties according to the minimum description length principle. We demonstrate that ACNML compares favorably to a number of prior techniques for uncertainty estimation in terms of calibration on out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-11-05T08:04:34Z)
• Generalized Sliced Distances for Probability Distributions [47.543990188697734]
  We introduce a broad family of probability metrics, coined as Generalized Sliced Probability Metrics (GSPMs) GSPMs are rooted in the generalized Radon transform and come with a unique geometric interpretation. We consider GSPM-based gradient flows for generative modeling applications and show that under mild assumptions, the gradient flow converges to the global optimum.
  arXiv  Detail & Related papers  (2020-02-28T04:18:00Z)
• Compact convex structure of measurements and its applications to simulability, incompatibility, and convex resource theory of continuous-outcome measurements [0.0]
  We define the measurement space $mathfrakM(E)$ as the set of post-processing equivalence classes of continuous measurements on $E. We show that the robustness measures of unsimulability and incompatibility coincide with the optimal ratio of the state discrimination probability of measurement(s) relative to that of simulable or compatible measurements.
  arXiv  Detail & Related papers  (2020-02-10T02:42:11Z)

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.