Physics-Aware Learnability: From Set-Theoretic Independence to Operational Constraints
This addresses foundational issues in machine learning theory for researchers dealing with non-standard data types like quantum or infinite-precision settings, though it is incremental in refining existing learnability frameworks.
The paper tackles the logical fragility of learnability beyond binary classification by introducing physics-aware learnability (PL), which defines learnability relative to explicit physical protocols, making previously paradoxical examples provably learnable with explicit sample complexity bounds. For quantum data, it reduces sample size to copy complexity and yields Helstrom-type lower bounds, with PL feasibility becoming decidable for finite no-signaling and quantum models.
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.