Physics-Aware Learnability: From Set-Theoretic Independence to Operational Constraints

Jeongho Bang; Kyoungho Cho

cs.LGFeb 28, 2026

Physics-Aware Learnability: From Set-Theoretic Independence to Operational Constraints

Authors: Jeongho Bang, Kyoungho Cho

Organizations: Institute for Convergence Research and Education in Advanced Technology, Yonsei University, Seoul 03722, Republic of Korea · Department of Quantum Information, Yonsei University, Incheon 21983, Republic of Korea · Department of Statistics and Data Science, Yonsei University, Seoul 03722, Republic of Korea

Abstract

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.

Figures & tables

Figure 1: Schematic of physics-aware learnability (PL). A learning task is specified by $(\Theta,\mathcal{H},U)$ : environments $\theta\in\Theta$ , a representable (finitely nameable) hypothesis set $\mathcal{H}$ , and a utility $U(\theta,h)\in[0,1]$ . A physical access model fixes, for each resource budget $d$ , a set $\mathfrak{L}_{d}$ of admissible input–output behaviors, represented as Markov kernels $Q(\cdot|\theta)\in\Delta(\mathcal{H})$ . Any concrete protocol—possibly randomized, adaptive, quantum, or distributed—induces exactly one such kernel; convexity and closure under classical post-processing capture free randomization and classical relabeling of outcomes. PL asks whether there exist $d$ and $Q\in\mathfrak{L}_{d}$ such that, uniformly for all $\theta$ , the output $H\sim Q(\cdot|\theta)$ achieves near-optimal performance with high probability, $\Pr[U(\theta,H)\geq\mathrm{opt}_{\mathcal{H}}(\theta)-\epsilon]\geq 1-\delta$ , where $\mathrm{opt}_{\mathcal{H}}(\theta)=\sup_{h\in\mathcal{H}}U(\theta,h)$ . This relocates the existential quantifier from arbitrary set-theoretic maps on samples to operational behaviors at the laboratory boundary: the objective $U$ (what counts as success) is held fixed while the admissible physics enters only through $\mathfrak{L}$ . Different choices of $\mathfrak{L}$ recover classical i.i.d. sampling, finite-precision coarse-graining interfaces, $d$ -copy quantum access (POVM-induced kernels), or finite no-signaling models; accordingly, $d$ becomes a genuine resource complexity (samples/copies/queries) that can both eliminate unphysical independence phenomena and expose genuine information-theoretic limits.

Figure 2: Schematic of physics-aware learnability (PL). A learning task $(\Theta,\mathcal{H},U)$ is paired with a physically specified access model that determines, for each sample budget $d$ , a set $\mathfrak{L}_{d}$ of admissible conditional output laws $Q(\cdot\mid\theta)$ . PL learnability asks whether some $Q\in\mathfrak{L}_{d}$ achieves near-optimal utility with high probability uniformly over environments.

Figure 3: Quantum instantiation of PL. Under $d$ -copy access to an unknown state $\hat{\rho}_{\theta}$ , any admissible protocol reduces to a POVM $\{\hat{M}_{h}\}_{h\in\mathcal{H}}$ on $\hat{\rho}_{\theta}^{\otimes d}$ followed by classical post-processing ( Theorem 10 ). The copy budget $d$ is a physical resource due to the no-cloning theorem ( Theorem 7 ).

Figure 4: Coarse-graining reduction. A finite-precision interface $\pi:\mathcal{X}\to\mathcal{Y}$ induces a pushforward distribution $Q=\pi_{\#}P$ on the countable alphabet and a pulled-back hypothesis class $\pi^{-1}(\mathcal{G})$ on $\mathcal{X}$ . The identity $P(g\circ\pi)=Q(g)$ (Eq. 75 ) implies that learning on $\mathcal{Y}$ yields PL learning on $\mathcal{X}$ under coarse-grained access (Theorem 11 ).

Explore similar work

What is Learnable in Valiant's Theory of the Learnable?
May 13, 2026Steve Hanneke, Anay Mehrotra, Grigoris Velegkas +1PAC Learning Statistical Learning Theory
Purdue University · Stanford University · Google Research +1
Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries
Sep 29, 2026Natsuto Isogai, Satoshi Yoshida, Mio MuraoSample Complexity Quantum Machine Learning
Department of Physics, Graduate School of Science, The University of Tokyo, Tokyo, Japan
Wide Learning: Learning to Reach Evidence
Aug 30, 2026Junzhou ChenEvidence-Grounded Reasoning Statistical Learning Theory
School of Intelligent Systems Engineering, Sun Yat-sen University Shenzhen 518107, China

May 13, 2026J/K move · Enter open · S save

What is Learnable in Valiant's Theory of the Learnable?

Steve Hanneke, Anay Mehrotra, Grigoris Velegkas, Manolis Zampetakis

Purdue University · Stanford University · Google Research+1

PAC Learning Statistical Learning Theory

Open paper AskPDF arXiv

Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only positives, may issue membership queries, and must output a hypothesis with no false positives. Prior work characterized variants, including the case without queries. We revisit Valiant's original model and ask: Which classes are learnable in it? For every finite domain, including Valiant's Boolean-hypercube setting, we show that a class is learnable if and only if every realizable positive sample can be certified by a poly-size adaptive query-compression scheme. This is a new variant of sample compression where the learner certifies samples via a short interaction with the membership oracle. Our characterization shows that learnability in Valiant's model is strictly sandwiched between learnability in the PAC model and the variant of Valiant's model without membership queries. This is one of the rare cases where introducing membership queries changes the set of learnable classes, and not just the sample or computational complexity. Next, we study the natural extension of the model to arbitrary domains. While we do not obtain an exact characterization, our techniques readily generalize and show that the same strict sandwiching persists. Finally, we show that

d

-dimensional halfspaces, which are not learnable without queries, are learnable with queries: we give a

\mathrm{poly}(d) \tilde{O}(1/ε)

sample and

\mathrm{poly}(d) \mathrm{polylog}(1/ε)

query algorithm, and prove that at least

Ω(d)

samples or queries are necessary. To our knowledge, this is the first algorithm for halfspaces in Valiant's model. Together, these results uncover a surprisingly rich theory behind Valiant's original notion of learnability and introduce ideas that may be of independent interest in learning theory.

Abstract

Explore similar work

What is Learnable in Valiant's Theory of the Learnable?

Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries

Wide Learning: Learning to Reach Evidence