1id1.net
Research paper · Preprint

Learning Orthant Comparability: Proper–Improper Separation and Compression without Side Information

1id1:core:20261120-0001@v1

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.

Learning theorySample compressionOrthant ordersSigned graphs

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

FileSize
Paper PDF565 KB
LaTeX source archive546 KB
SHA-256 checksums
paper.pdf
73823086e7a740f4cf25c1f3670974c66a59dd2a17a181afaff37ccd21fd009c
source.zip
9d5d7bd7314286dc7bf400e2fe9783dc99c913c417880ada437cc3af4c6308c6

Version history

v1Initial deposit

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.