Physics-Aware Learnability: From Set-Theoretic Independence to Operational Constraints
Beyond binary classification, learnability can become a logically fragile notion: in EMX, even the class of all finite subsets of $[0,1]$ is learnable in some models of ZFC and not in others. We argue the paradox is operational. The standard definitions quantify over arbitrary set-theoretic learners that implicitly assume non-operational resources (infinite precision, unphysical data access, and non-representable outputs). We introduce physics-aware learnability (PL), which defines the learnability relative to an explicit access model -- a family of admissible physical protocols. Finite-precision coarse-graining reduces continuum EMX to a countable problem, via an exact pushforward/pullback reduction that preserves the EMX objective, making the independence example provably learnable with explicit $(ε,δ)$ sample complexity. For quantum data, admissible learners are exactly POVMs on $d$ copies, turning sample size into copy complexity and yielding Helstrom(-type) lower bounds. For finite no-signaling and quantum models, PL feasibility becomes linear or semidefinite and is therefore decidable.
Code (0)
등록된 구현이 없습니다.
Tasks
Binary ClassificationSimilar Papers 제목 키워드 기반
Learnability Can Be Independent of ZFC Axioms: Explanations and Implications
In Ben-David et al.'s "Learnability Can Be Undecidable," they prove an independence result in theoretical machine learning. In particular, they define a new type of learnability, called Estimating The Maximum (EMX) learn…
From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability
Machine learning researchers and practitioners steadily enlarge the multitude of successful learning models. They achieve this through in-depth theoretical analyses and experiential heuristics. However, there is no known…
BIG-bench Machine LearningBinary ClassificationOn the Limitation and Experience Replay for GNNs in Continual Learning
Continual learning seeks to empower models to progressively acquire information from a sequence of tasks. This approach is crucial for many real-world systems, which are dynamic and evolve over time. Recent research has …
Continual LearningIncremental LearningModel SelectionOn the Learnability of Deep Random Networks
In this paper we study the learnability of deep random networks from both theoretical and practical points of view. On the theoretical front, we show that the learnability of random deep networks with sign activation dro…
Physics-aware Reduced-order Modeling of Transonic Flow via $β$-Variational Autoencoder
Autoencoder-based reduced-order modeling (ROM) has recently attracted significant attention, owing to its ability to capture underlying nonlinear features. However, two critical drawbacks severely undermine its scalabili…