Abstract
We study learning coordinate-reversed product orders from undirected comparability feedback. For the resulting class of VC dimension d−1, a polynomial-time proper realizable PAC learner would imply RP = NP, even when negative examples have support three. In contrast, the closure of positive examples is an efficient improper learner, with at most d−1 online mistakes and sample complexity O((d + log(1/δ))/ε). Every realizable mixed sample compresses to at most d−1 positive examples, without side information. An affine version space represented by a signed graph yields computable PAC-Bayes bounds. For dependent pairs drawn from continuous product distributions, the paper also establishes Poisson and coupon-collector thresholds.
Cite this version
Wuming Pan. Learning Orthant Comparability: Proper–Improper Separation and Compression without Side Information. 1id1, v1, 20 November 2026. 1id1:core:20261120-0001@v1. https://1id1.net/id/core/20261120-0001/v1/
Files & integrity
| File | Size |
|---|---|
| Paper PDF | 565 KB |
| LaTeX source archive | 546 KB |
SHA-256 checksums
Version history
First fixed 1id1 preprint. The main PDF is 24 pages; the 11-page supplement is included as Supplement.pdf in the source archive, together with the typesetting sources, the Lean development and the finite verification program.
Provenance & verification
Author preprint; not a peer-reviewed publication. AI assistance is disclosed in the manuscript. This record does not claim an arXiv identifier.
The main paper and supplement were compiled for this release. The Lean development checks the mathematical content of Theorem 4.2(a,c) and Theorem 4.3; it does not certify running times or proper-learning hardness. Its Theorem 4.4 PAC result is restricted to finitely supported distributions. See the supplement and FORMALIZATION_SCOPE.txt in the archive.