Proof-Carrying Optimality for Finite Identification under Bounded Adversarial Answer Errors

Source abstract

Abstract Exact learning from queries is a model of machine learning in which a learner actively identifies an unknown hypothesis. We study its finite, realizable form when queries come from a declared alphabet and an adversary may corrupt a bounded number of answers. For this setting we develop independently checkable certificates of exact worst-case query complexity. Portable certificates combine a noiseless strategy with a lower witness to prove an affine identity for every error budget, without expanding the corrupted-answer game. An isolation witness consists of classes on which each permitted probe agrees on all but at most one class. We prove its exact value for arbitrary residual error budgets and match it to a known robustification bound. Expanded strategy and adversary certificates handle individual budgets; separate distance and rational-dual certificates establish non-adaptive optima. Isolation witnesses increase compact coverage from 4 to 9 of 15 primary tables and from 25 to 69 of 101 sweep tables. Combined evidence certifies 302 of 303 sweep cells at budgets zero, one, and two. An additional 256-table evaluation increases compact coverage from 71 to 161; constructed certificates reach 256 classes. As a learning example, identifying a monotone conjunction of four variables with two corrupted answers requires exactly 14 adaptive queries versus 20 non-adaptive queries. The contribution is a certification method for finite query learning and its computational study; the singleton-search and robustification formulas are established prior results.