Explanation-Assisted Learning with Adaptive Witnesses

An explanation can tell a learner how to classify examples beyond the one being explained. We study explanation-assisted learning when several explanations are valid and a provider uses the training history to choose which one to reveal. We model explanations as reusable positive witnesses: a positive training input is a bag of instances, and its explanation identifies an instance sufficient for positivity. Test bags have no witnesses. At latent VC dimension one, a learner whose output is independent of witness selection achieves the optimal memoryless sample complexity. At dimension two, a family separates the sample complexities of memoryless explanations, causal explanations, and labels alone; a countable extension separates PAC learnability itself. The lower-bound provider always gives valid explanations, yet its complete witness history carries no information about unseen designated labels beyond the observed labels. Finite Littlestone dimension gives a general causal upper bound, while a witness-span learner for linear subspaces attains the memoryless rate.