acceptodds
Under review as a conference paper at ICLR 2027

Explanation-Assisted Learning with Adaptive Witnesses

Abstract

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.

Primary area:
learning theory
Keywords:
Explanation-assisted learning, PAC learning, adaptive witness selection, sample complexity

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_PbxMOpenReview ↗
Rating
3
Confidence
1
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This theoretical paper studies learning with explanations modeled as positive witnesses: each input / sample is a collection of items, and an explanation identifies one item sufficient for a positive label. It investigates how history-dependent witness selection affects sample complexity, proving separations from memoryless selection and giving conditions under which the learning benefit is preserved.

My assessment is mostly an educated guess because this work lies outside my main expertise. Unfortunately, the authors did not attempt to make the paper self-contained and understandable for people of various backgrounds. I have not identified a specific correctness issue, but I could not independently verify the central proofs. As a result, the soundness score should be read with that limitation.

Critical strengths
  • The paper formulates a precise question about whether valid explanations (under the chosen semantics) remain useful when their selection depends on training history.
  • The stated results look interesting from the learning theory perspective.
Critical weaknesses
  • To my taste, the paper's presentation is not great and leaves much to be desired, from the perspective of an average reader. While definitions and proof sketches are provided, I found the central construction hard to follow without substantial background in learning theory.
  • The connection between the witness abstraction and explanations used in practical classification is insufficiently developed. A worked example using ordinary feature-based inputs would help.
  • The main separation relies on a highly constructed family with very large bags, making its implications for realistic learning settings unclear.
Questions for authors
  • How does this framework relate to learning from abductive explanations expressed as sufficient partial feature assignments? Can the separation be demonstrated in a typical ML classification setup?
  • What conclusions still apply when bag size is realistically bounded?
4 comments
AuthorsOpenReview ↗

Reply to Reviewer PbxM(1/3)

Dear Reviewer PbxM,

Thank you for your careful reading and candid assessment, and for the concrete suggestions on a worked example and on abductive explanations. They shaped several revisions, marked in blue in the revised PDF; "new" below refers to results added in the new Appendix H.

W1 (presentation)

Thank you for this comment. We agree that the original version was hard to follow for readers outside learning theory, and we first restate the paper in machine-learning terms.

Problem. Training labels increasingly come with explanations, such as annotator rationales. A rule that explains one example can also label future examples, so explanations can reduce the number of labels needed. An input, however, often has several valid explanations, and which one is shown may depend on the annotation history, for example when annotators stay consistent with their earlier answers. We ask whether the label savings from valid explanations survive when the choice among them depends on this history.

Findings. First, explanations chosen by any fixed criterion that ignores earlier annotations, such as the shortest, first, or most salient valid one, reduce the labels needed, and the cost depends on the complexity of the explanation rules rather than of the classifier. Second, history dependence is harmless in several natural cases, namely the simplest rule families, linear subspaces, and sparse rule dictionaries, where an input is positive if any of a few unknown key features is present. Third, it is not harmless in general. For some rule families, a history-dependent annotator can give only valid, even minimal, explanations that together reveal nothing about unseen examples beyond the labels, so many more labels are needed. Such a loss requires a very large number of candidate rules.

Approach. We study sample complexity, the number of labeled examples needed to reach a given accuracy, with labels alone, with explanations chosen by a fixed criterion, and with explanations chosen depending on the history. Explanations are modeled as sufficient reasons, or abductive explanations, over a dictionary of rules. Our guarantees hold for every valid choice of explanation, because a learner can check that an explanation is valid but cannot verify the annotator's intent.

Implications. For annotation design, a fixed selection criterion is always safe, and in sparse-rule settings any selection is safe. For explainability, the validity, or even minimality, of each explanation does not guarantee that a set of explanations is informative; when explanations are reused as supervision, how they are selected across examples matters.

Changes for readability. The second paragraph of the introduction now gives a worked feature example (see W2), and Section 2.1 maps it onto the model with a table. The detailed dimension arguments of Section 4.3 have moved to Appendix C.2, and a new related-work paragraph connects our explanations to abductive explanations. The central construction rests on one idea, which Section 4.1 explains before the formal details. Every explanation is valid, but the code it carries is masked by a random pad, as in a one-time pad, so a learner who sees all explanations learns nothing about the labels of the unseen designated bags beyond what the observed labels reveal (Proposition 4.2).

AuthorsOpenReview ↗

Reply to Reviewer PbxM(2/3)

W2 (connection to practical explanations; a worked feature example)

Thank you for this suggestion; we agree. The revision adds such an example in the second paragraph of the introduction and maps it onto the model in Section 2.1. Take three binary features and two rules, a = x₁∧x₂ and b = x₂∧x₃, each sufficient for a positive label.

  • On x = (1,1,1), both rules fire, so an annotator can correctly explain the positive label by citing either one.
  • On x' = (0,1,1), only b fires. A learner told b on x can label x' positive without seeing its label; a learner told a cannot.

The two explanations are equally valid on x, yet carry different information about future inputs. Which one is shown may depend on what the annotator explained before, and this choice is what the paper studies. In our model an input is represented by the set of rules that fire on it, A(x) = {a, b} and A(x') = {b}. The unknown target G is the set of rules sufficient for a positive label, here {a, b}, and an explanation (a witness) is one rule in A(x) ∩ G. In general, input x ↔ bag A(x) of rules that fire, rule ↔ instance, rules sufficient for positivity ↔ target G, and explanation ↔ witness.

Rules can be any checkable conditions on features, such as conjunctions of feature values or the presence of a phrase or substructure. In text classification with rationales, for example, a document is positive if it contains any of a few unknown key phrases, and the annotator highlights one key phrase it contains. When the highlighted phrase alone suffices for the label, it is exactly a witness. This is the sparse-rule setting of Section 5.3 (new Proposition H.4), where explanations reduce the labels needed under any annotator behavior.

W3 and Q2 (the constructed family; realistic bag sizes)

Thank you for raising this concern and the related question. We agree that the separating family is highly constructed and that its inputs are very large. Its role is to answer a worst-case question, whether valid explanations alone guarantee the label savings whatever the annotator's selection, and it shows that they do not. New Proposition H.3 shows that large inputs are necessary for any such loss, which needs many rules firing on an input and a very large rule dictionary.

This also answers what holds when inputs are realistically bounded. If at most b rules fire on any input, history dependence costs at most a factor of order log b in labels compared with a fixed selection criterion. Learning then never becomes impossible, as it does in our countable extension, which needs unbounded inputs. When only one rule fires, the explanation is forced and all annotator behaviors coincide. All positive results hold at any input size. Any fixed selection criterion is safe, and every annotator behavior is safe for sparse rule dictionaries, for the simplest rule families and for linear subspaces. We know of no natural annotator behavior that is harmful, and Section 6 now asks whether one exists.

AuthorsOpenReview ↗

Reply to Reviewer PbxM(3/3)

Q1 (abductive explanations; a typical ML setup)

Thank you for this question, which connects the paper to formal explainability. Our explanations are abductive explanations of the target. An abductive explanation (a minimal sufficient reason, or prime implicant) of a positive input is a minimal partial feature assignment that forces a positive label whatever the remaining features are. In the example of W2, with f = (x₁∧x₂) ∨ (x₂∧x₃) and x = (1,1,1), the abductive explanations of f at x are exactly {x₁=1, x₂=1} and {x₂=1, x₃=1}, that is, the rules a and b, the two valid explanations in our model. New Proposition H.2 shows that this holds in general when each input is encoded by one Boolean feature per rule, indicating whether the rule fires. The target is then a disjunction of these features, and the minimal sufficient reasons of a positive input, even allowing features fixed to zero, are exactly its valid explanations in our model. Our framework is thus learning from abductive explanations of the target concept, rather than of a trained model, with one abductive explanation per positive example. Requiring minimal explanations removes none of the annotator's choices, and all results hold verbatim. The freedom we study is that an input often has several abductive explanations, as x does above.

The separation can be demonstrated in this feature form. Under this encoding, the family of Section 4 is a binary classification problem over Boolean features in which every explanation the annotator gives is a minimal abductive explanation, and Theorem 4.1 holds unchanged. The encoding needs a very large number of features, and by new Proposition H.3 this is true of any separation, not only ours (see W3 and Q2). In typical setups the conclusion is positive. When an input is positive iff it contains any of at most s unknown key features out of N candidates, explanations reduce the labels needed from order s log(N/s) to order s for every annotator behavior, including history-dependent ones (new Proposition H.4). If instead the target is a disjunction of at most s short conjunctions of raw features and each explanation names one satisfied conjunction, O((s+log(1/δ))/ε) samples suffice for every annotator behavior, independently of the number of features and of the length of the conjunctions (Appendix H.4).

Thank you again for your review; we would be glad to clarify anything further.

Thank you for the constructive responses. I appreciate it.

Reviewer_hK9qOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper models an explanation as a reusable positive certificate. An input is a bag of instances, and it is positive when it meets an unknown set G drawn from a known finite family. Each positive training bag comes with a witness, which is one instance in the bag that also lies in G. Test bags carry no witness. The question is what happens when the provider picks among several valid witnesses using the training history. With a memoryless provider, which uses a fixed kernel and fresh coins, the records are i.i.d. A reduction to robust learning then gives the rate Θ((β + log(1/δ))/ε), where β is the latent VC dimension on instances, in place of the bag VC dimension. With a causal provider, the witness may depend on earlier records.

The main results are as follows. At β = 1 there is a deterministic tree-gate learner. It maps every legal witness for a bag to the same subtree of a compatible-split tree, makes at most one leave-one-out error on any pool, and achieves the memoryless rate against every causal provider. At β = 2 there is an affine prefix family over GF(2^q) whose memoryless, causal and label-only sample complexities have numerators 1, q and q^2. One deterministic provider produces a witness transcript that adds nothing to the posterior on unseen designated labels beyond what the labels already give. A countable disjoint union of these families is PAC learnable under memoryless providers but not under deterministic causal ones. On the positive side, Littlestone dimension gives a general causal upper bound through online-to-batch conversion. For linear subspaces, a witness-span learner attains Θ((d + log(1/δ))/ε). The paper is purely theoretical and has no experiments.

Critical strengths
  1. The β = 1 result is correct, and the reason it works is useful. Lemma B.2 shows that every legal witness for a positive bag points to the same component of the tree after the negative hull is removed. As a result the learner's output is a function of the bags alone, and a one-inclusion style leave-one-out argument goes through unchanged under arbitrary history-dependent selection. I implemented the compatible-split tree, the canonical constraints of equation 11 and the gate rule of equation 13. Across 2647 pool and witness configurations on 40 random VC-one classes, no constraint depended on the witness, and the maximum number of leave-one-out errors was exactly 1. An exact computation of expected risk also never exceeded 1/(m+1). The binary-path proposition shows a real gap from labels alone, d against 1.

  2. The VC-two separation is the paper's most interesting contribution, and the hard parts check out. The provider assigns a fresh pad to each newly discovered positive bag, so every line is evaluated at only one public point per history. The cap of q minus 2 on the number of pads keeps deep tokens out of shattered triples. I verified VC(G_q) = 2 by exhaustive search over every co-occurring triple: 3736 triples for q = 3 and 11129984 triples for q = 4 over GF(16), with no shattered triple. Littlestone dimension comes out at exactly 3 and 4. Proposition 4.2 holds exactly under both a uniform and a random nonuniform prior. A memoryless depth-one provider on the same family does leak, with posterior shifts up to 0.95, which is precisely the contrast the paper claims. The tail calculation in Appendix C.3 is also right. Markov's inequality gives at least 3/4 for the event that at most half the rare bags have been seen. A Chernoff bound with η = 7/8 gives a conditional factor above 3/4. Their product exceeds (3/4)^2 = 0.5625, which is above 1/2.

Critical weaknesses
  1. The significance of the negative result is limited by how pathological its construction is, and the paper does not characterize the causal regime beyond β = 1 and a few specific families. Tokens are indexed by ordered discovery histories and codes over GF(2^q), so instance identity serves as a covert channel. My count from equation 45 gives designated bags of size about 2^300.6 at q = 17, the smallest q in Theorem 4.1. The authors concede on page 9, near line 476, that the "construction requires very large bags", and for bag size b they leave the worst-case numerator at latent VC dimension two between the square root of log b and log b, asking "Can this gap be closed?" on page 9, near line 479. On the positive side, the only general tool for β ≥ 2 is Littlestone dimension, and the paper itself shows that it does not govern the causal rate: Proposition B.5 gives Littlestone dimension d with causal numerator 1, and page 9, near line 438, notes that "a disjoint union of binary-path families with unbounded depth has infinite L" yet stays learnable. So for β ≥ 2 the reader gets one upper bound, one tailored lower-bound family and the subspace case, with no dimension that governs m⋆cau. Table 1's column header, "Governing dimension on this family", reads correctly only with that qualifier. For ICLR, the practical message for annotator rationales comes down to this: fix your selection rule. That is useful advice, but it follows from Proposition 2.1 alone.

  2. Part of the memoryless benchmark rests on very recent, unrefereed work, and the conclusion states it without the caveat. Proposition 2.1 claims Θ((β + log(1/δ))/ε) for every β, and page 3, near line 153, says "the general additive dependence follows from Montasser (2026)", which is arXiv 2608.13514. I checked that this preprint exists: Montasser, submitted 13 August 2026, with a realizable Theorem 1 matching the paper's restatement in which the dual dimension controls the number of oracle calls. The self-contained route, Lemma A.1 and Corollary A.2 built on Lemma 5 of Aden-Ali et al. 2024, yields β(1 + log(1/δ))/ε, so it matches the stated rate only for β ≤ 2. To their credit, the authors disclose this on page 3 and again in Appendix G. The main results are unaffected, because the affine family has β = 2 and Proposition 5.2 is proved directly, and even the self-contained bound is free of the bag dimension. Still, the conclusion on page 9, near line 461, says Proposition 2.1 gives optimal memoryless sample complexity for any fixed rule, and for β > 2 that optimality depends on a preprint about six weeks older than the deadline. The caveat belongs there too. This is a minor point next to the first weakness.

Questions for authors
  1. Can the causal separation survive with bag size polynomial in q, or with |R_q| at most 2^{O(q)}? If the authors have even a partial answer, I would read the negative result as structural rather than as an artifact of encoding.
  2. Is there a dimension that characterizes m⋆cau, for example one interpolating between the latent VC dimension and Littlestone dimension, consistent with both the binary-path family and G_q?
  3. How does this model relate to discriminative feature feedback, Dasgupta, Dey, Roberts and Sabato, NeurIPS 2018, and its robust follow-ups by Dasgupta and Sabato and by Sabato? There the teacher supplies a feature separating the current instance from a previously seen one of a different label, and mistake bounds are proved. I believe those guarantees hold for any valid feature the teacher picks, which would make them close in spirit to the uniform-over-providers guarantees here, so a comparison would help position the contribution. A full-text search found no citation of that line.
4 comments
AuthorsOpenReview ↗

Reply to Reviewer hK9q(1/2)

Dear Reviewer hK9q,

Thank you for an exceptionally careful review. We are grateful that you implemented and checked the β = 1 learner and the VC-two construction, including the exhaustive VC checks at q = 3 and 4, the Littlestone dimensions, the posterior identity and the tail calculation, and that you separated correctness from significance. Your questions led to new Proposition H.3 and to several revisions, marked in blue in the revised PDF. W1 raises three points, the first two of which are also Q1 and Q2, so we answer them together.

W1(a) and Q1 (size of the construction; polynomial bags; |R_q| = 2$^{O(q)}$)

Thank you for this question and for checking the size; your count, log₂|A_i| ≈ 300.6 at q = 17, matches eq. (45). We agree that Theorem 4.1 shows the limit of validity alone on one constructed family, and that the question is how much of its size the problem forces. New Proposition H.3 gives a partial answer. Part of the size is structural, because every separation needs exponentially large inputs. Both ingredients of H.3 were already in Appendix F.2.

(i) On bags of size at most b, ignoring witnesses and using the MIL bound (57) gives m*{cau} ≤ m*{lab} = O((β log(2b)+log(1/δ))/ε) against every causal provider.

(ii) Theorem 5.1 with Sauer's lemma gives m⋆cau_{cau} = O((β log(e|R|/β)+log(1/δ))/ε).

At β = 2, a gap linear in q therefore requires b and |R| of size 2$^{Ω(q)},sopolynomial−sizebagscannotsupportit.Agapthatgrowswithbdoessurviveeverybag−sizebudget.Instantiatingourfamilyatq≍√logbgivesacausalnumeratoroforder√logb,sowithpoly(q)−sizebagstheattainablegapliesbetweenΩ(√logq)andO(logq).Part(i)alsoshowsthatCorollaryC.2needsunboundedbagsizes,whichSection4nowstates.For∣R∣=2, so polynomial-size bags cannot support it. A gap that grows with b does survive every bag-size budget. Instantiating our family at q ≍ √log b gives a causal numerator of order √log b, so with poly(q)-size bags the attainable gap lies between Ω(√log q) and O(log q). Part (i) also shows that Corollary C.2 needs unbounded bag sizes, which Section 4 now states. For |R| = 2^{O(q)},thefull1/q/q2tripleisimpossible,since(i)withb=∣R∣capsthelabel−onlynumeratoratO(q).Whethera1−versus−qgapsurvivesthereisopen,andwehavenoprogressonityet;itisexactlythesquaregapbetweenour2, the full 1/q/q² triple is impossible, since (i) with b = |R| caps the label-only numerator at O(q). Whether a 1-versus-q gap survives there is open, and we have no progress on it yet; it is exactly the square gap between our 2^{Θ(q²)}$ construction and the 2$^{Ω(q)}$ necessity.

On instance identity as a covert channel, we agree that this is the channel the construction uses. In our model an explanation is the identity of the instance it names (Section 2.1), so the provider's only freedom is which valid instance to name, and the construction uses exactly this freedom. By new Proposition H.2, these instances are the minimal sufficient reasons of the input over rule indicators, so such a channel exists whenever an input has several minimal explanations. The masking is exact and needs no computational assumption (Proposition 4.2).

W1(b) and Q2 (a characterizing dimension)

Thank you for this question and for the remark on Table 1. We do not have such a dimension, and Table 1's last column now reads "Dimension matching the rate on this family". The revision narrows the question. Any candidate must be constant on all VC-one classes even when Ldim is unbounded, Θ(q) on 𝒢_q, and between β and min{Ldim, v_{bag}}. We agree with the point implicit in your question. Beyond β = 1, every family in the paper on which history dependence costs nothing (subspaces, sparse rules, and the closure-chain condition in Appendix H.4) has Ldim = β. These families therefore do not separate β-type from Ldim-type candidates, and β = 1 remains the only case where the causal rate is shown to fall below Ldim. Whether some family with β ≥ 2 and Ldim ≫ β costs nothing under every causal provider is open, and we see it as the natural next step.

AuthorsOpenReview ↗

Reply to Reviewer hK9q(2/2)

W1(c) (the practical message)

Thank you for distilling the practical message. We agree that "fix your selection rule" follows from Proposition 2.1; the rest of the paper adds when this advice is needed and how much is at stake. First, several results might suggest that validity alone suffices, namely guarantees that hold uniformly over valid feedback (DFF mistake bounds, our Theorem 5.1), the β = 1 theorem, the subspace result and the new sparse-rule result. Theorem 4.1 and Corollary C.2 show that it does not for some families of latent VC dimension two. Second, at β = 1, for subspaces and for sparse rule dictionaries, every history-dependent selection attains the memoryless order, so there the advice is not needed. Third, by Proposition H.3, history dependence costs at most a factor O(log(2b)) on bags of at most b instances. We agree that necessity is shown only on a constructed family, which by H.3 must use exponentially large inputs. We know of no natural history-dependent rule that is harmful, and Section 6 now asks whether one exists.

W2 (reliance on Montasser, 2026)

Thank you for checking the preprint and for pointing out where the caveat was missing. We agree, and the conclusion sentence you quote (Section 6) now states that, for β > 2, this optimality relies on the recent preprint of Montasser (2026). The self-contained route gives O(β(1+log(1/δ))/ε) (Corollary A.2), which matches the stated rate for β ≤ 2, and the same caveat applies to the matching order in new Proposition H.1 for β > 2. As you note, the main results do not depend on the preprint. Theorems 3.1 and 4.1, Corollary C.2, and Propositions 5.2 and H.4 are proved directly, and even the self-contained bound replaces the bag dimension by β.

Q3 (discriminative feature feedback)

Thank you for pointing us to this line of work. We had missed it, and the revision now discusses it in the related work (Section 1.2). You are right that DFF mistake bounds hold for any valid feature, and hence for any history-dependent teacher, so they are close in spirit to our uniform-over-providers guarantees. The two differ in setting and in the rate at stake. DFF is online, and after each mistake the teacher gives a feature that separates the current instance from a previously seen one with a different label. Our feedback is a certificate inside the current input, and our setting is i.i.d. PAC learning. Mistake bounds hold against every sequence, so they are robust to selection automatically, and online-to-batch conversion turns a mistake bound M into a rate of order (M+log(1/δ))/ε. Our Theorem 5.1 is of this type, with M the Littlestone dimension. The question we add is whether the smaller i.i.d. rate, governed by the latent VC dimension β, survives history-dependent selection among valid certificates; on 𝒢_q, for instance, L = q while β = 2. It survives at β = 1, for subspaces and for sparse rule dictionaries, but not in general (Theorem 4.1). The robust DFF variants are also a natural template for noisy explanations, which Section 6 lists as a limitation.

Thank you again for the careful review; we would be glad to discuss any of these points further.

I acknowledge I have read the rebuttal. I have decided to keep my score.

AuthorsOpenReview ↗

Follow-up to Reviewer hK9q

Dear Reviewer hK9q,

Thank you for reading our response. Before the discussion closes on November 18, could you let us know which concerns remain, so that we can still address them?

In Q1 you wrote that even a partial answer would make you read the negative result as structural rather than as an artifact of encoding. New Proposition H.3 gives that answer. On bags of at most b instances, history dependence costs at most a factor O(log(2b)) for every finite family and causal provider, so the exponential input size is forced by the problem, not by our encoding; and the separation survives every bag-size budget, with a gap of order √log b. The other points (the Montasser caveat in the conclusion, the Table 1 header, and the DFF discussion) are fixed in the revision.

If H.3 does not change your reading, we would be grateful to know what would.

Best regards, The authors

Reviewer_EbuNOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper analyzes a type of PAC learning in which each training example which is positive comes with an “explanation”, or a “witness”: a single element of the input (for example, a rule that fires on it) that aligns and certifies the positive prediction. The setting can be seen as a type of teacher-student learning, where the teacher provides valid explanations of the target and the student aims to learn to predict it. The authors perform an analysis of this setting in the worst case, i.e., over all teachers that give valid explanations. They first look at a “memoryless” benchmark: when the teacher’s choice of the explanation does not depend on previous examples, the sample complexity is reduced from the complexity of the input-level class to that of the explanation-level class. They then study a history-dependent setting with witness selection in two scenarios. When the latent VC dimension is 1, they give a learner whose output doesn’t depend on what valid witness is provided, so the history-dependent selection does not incur cost. When it is 2, they construct a family on which the history-dependent provider, while always giving valid witnesses, does not reveal anything beyond the labels. Finally, the authors give general upper bounds for the history-dependent providers via the Littelstone dimension, and provide an efficient optimal learner for linear subspaces.

Critical strengths
  1. The setting that is studied in this paper, where the explanations are used as part of the training data within PAC learning, is to my knowledge novel and can open the door to future work.

  2. Although the paper is framed in a very learning-theory-focused way, it is in overall well organized and well written in parts.

  3. The authors provide in the paper a rigorous separation between learning from memoryless witnesses, from the history-dependent witnesses, and from labels alone, together with a positive result showing that the history dependence is harmless at VC dimension that is equal to 1.

Critical weaknesses
  1. The adversarial framing is not well motivated. The results are all worst-case over all teachers that provide valid explanations, so the negative results are driven by a teacher that coordinates its explanations in a way that withholds some of the information. I understand the rationale for this (the learner can’t distinguish a helpful teacher from one that is manipulative), but in settings where explanations are used for training, it seems to me more likely that they would be chosen to improve learning. In particular, the annotators mentioned as motivation are usually not adversarial. For example, a cooperative teacher that deliberately chooses explanations to help, for example a history-aware one that avoids redundant explanations, is not studied in the paper, and it seems the more relevant case for practice.

  2. Limiting assumptions. The explanations are given only for positive predictions. It is not clear why negative predictions are not explained as well. In addition, explanations are assumed to be exact, and there is no setting with corrupted data points or noisy explanations that is studied.

  3. The benefit depends on an implicit restriction of the explanation language. All of the guarantees are stated in terms of the latent VC dimension, which depends on the universe of the possible allowed explanations. If “trivial” explanations can be allowed (e.g., the full input), the latent VC dimension is at least the complexity of the classifier itself, and the explanations do not provide any benefit. The paper does not discuss which natural explanation languages (e.g., bounded-size) give a small latent VC dimension in practice. The paper also does not discuss whether restricting providers to minimal explanations, as is common in the explainability literature, would remove their ability to hide information that is shown in the paper.

  4. No characterization of the history-dependent rate. Neither the VC dimension (by the dimension-2 separation) nor the Littlestone dimension (the binary-path example that is shown) characterizes the sample complexity under history-dependent teachers. Beyond these bounds and two special cases (VC dimension 1 and the linear subspaces), it remains unclear to me what governs this rate for a given class. Including such a characterization would improve the work.

  5. The separating construction is artificial. The family that is used for the separation is cryptographic and requires exponentially large inputs. It is not clear whether a similar separation holds for a natural class, which limits the relevance of the negative result. Also, the subspace rate already follows from the paper's own Littlestone bound, since the Littlestone dimension of that class equals its dimension. The contribution there is the computational efficiency rather than a new rate.

  6. Limited accessibility to the interpretability audience. The current framing makes the paper accessible to the learning-theory audience but not to the interpretability and explainability community, which limits its impact.

  7. Missing related work. Several relevant works are not discussed. First, the discriminative feature feedback model [1-3] studies learning from labels augmented with teacher-provided explanations and this line of work shows that they can reduce learning complexity. [4] treat explanations as realizability-based certificates, as this paper also does, but in the reverse direction (from learner to user) but is not discussed. Also, the witness model in this paper is essentially what the explainability literature calls a “sufficient reason” (or abductive explanation/prime implicant), studied for example in [5–7]. It also relates to the popular and common Anchors explanation method [8] that is not discussed. In that literature, the multiplicity of valid sufficient reasons per input, which is the very source of the freedom of the teacher here, is well studied (Weakness 3). Finally, the hiding construction that is discussed in the paper is relevant to work on reconstructing models from their explanations [9].

[1] Learning from Discriminative Feature Feedback (Dasgupta et al., NeurIPS 2018)

[2] Robust Learning from Discriminative Feature Feedback (Dasgupta et al., AISTATS 2020)

[3] Improved Robust Algorithms for Learning with Discriminative Feature Feedback (Sabato, AISTATS 2023)

[4] Proofs as Explanations: Short Certificates for Reliable Predictions (Blum et al., COLT 2025)

[5] Abduction-Based Explanations for Machine Learning Models (Ignatiev et al., AAAI 2019)

[6] On the Reasons Behind Decisions (Darwiche et al., ECAI 2020)

[7] Towards Formal XAI: Formally Approximate Minimal Explanations of Neural Networks (Bassan et al., TACAS 2023)

[8] Anchors: High-Precision Model-Agnostic Explanations (Ribeiro et al., AAAI 2018)

[9] Model Reconstruction from Model Explanations (Milli et al., FAT* 2019)

Questions for authors
  1. What would happen if we have a cooperative, history-aware teacher, what would it achieve (i.e., not the adversarial setting)? Can it improve the memoryless rate?

  2. Does the separation that is shown in the paper persist if teachers must return minimal (or bounded-size) explanations?

  3. Can this framework be extended to explanations of negative predictions, or to noisy explanations, which might be more realistic?

6 comments
AuthorsOpenReview ↗

Reply to Reviewer EbuN(1/3)

Dear Reviewer EbuN,

Thank you for the detailed review, for finding the setting novel and the separation rigorous, and for the precise questions and references. They led to four short new results (Propositions H.1–H.4 in a new Appendix H) and to several revisions, all marked in blue in the revised PDF. Each question is closely tied to one weakness, so we answer them together.

W1 and Q1 (adversarial framing; a cooperative, history-aware teacher)

Thank you for this question, which led to new Proposition H.1. In the worst case, a cooperative, history-aware teacher cannot improve the memoryless rate. Proposition H.1 lets the teacher be designed jointly with the learner and use the target, the distribution and the full history, provided every explanation is valid. Even then, the best learner–teacher pair needs Ω((β+log(1/δ))/ε) samples in the worst case, and a fixed selection rule already attains this order (Proposition 2.1; for β > 2 via Montasser, 2026). The reason is that the hardest distributions use only empty and singleton inputs, and a positive singleton has exactly one valid explanation, so every teacher, helpful or not, returns the same record. On a particular distribution where inputs have several valid explanations, a helpful teacher can do better, for instance by avoiding explanations the learner has already seen, as you suggest. We do not characterize this distribution-dependent gain, and we agree that it is an interesting direction.

We also agree that annotators are usually not adversarial, and our model does not assume that they are; the revised introduction now says so explicitly. History dependence can arise without malice, for example when an annotator stays consistent with earlier answers. Our guarantees take the form "one learner succeeds against every valid teacher", because validity is what a learner can check, while helpfulness cannot be verified from the explanations themselves. Such a guarantee covers cooperative teachers in particular, and a lower bound for it needs only one hard valid teacher. That is the only role of the teacher in our negative results, so the causal results measure what is lost when cooperation cannot be verified. On the separating family 𝒢q_q, a cooperative teacher, like any fixed selection rule, attains Θ((1+log(1/δ))/ε), whereas validity alone permits Θ((q+log(1/δ))/ε) (Theorem 4.1). The hard teacher is constructed for this purpose (its first explanation for an input encodes the order of earlier inputs), and we do not suggest that annotators behave this way. We know of no natural history-dependent rule that is harmful, and Section 6 now asks whether one exists, for example a teacher that repeats an earlier explanation whenever the input contains one.

W2 and Q3 (negative and noisy explanations)

Thank you for raising these two extensions; we agree that both matter in practice.

Negative explanations. In our OR model, a negative label already certifies that no rule in the input belongs to the target, so pointing to a rule in the input adds nothing. Informative explanations of negative inputs take other forms. In the rule-indicator encoding of Proposition H.2, an abductive explanation of a negative input must fix every target rule to 0, so it is unique and reveals the whole target, with no selection involved. A counterfactual explanation that names one target rule that does not fire leaves a choice, so our question would arise again in a different model. Under AND semantics, where an input is positive if every target rule fires, a negative input is naturally explained by a target rule that fails. Complementing each input in R and flipping the label maps this setting exactly onto ours, so for a finite rule set all our results, including Theorem 4.1, apply to such explanations. Section 6 now discusses negative explanations in our OR model.

Noisy explanations. We studied exact explanations as a first step, to separate the effect of selection from that of noise. Our lower bounds (Theorem 4.1, Corollary C.2) hold with exact explanations, so the separation is not caused by noise. Our positive results, in contrast, need exact certificates, since in canonicalization (Section 3) and witness spans (Section 5.2) a single invalid explanation can exclude the target. With exact labels, a learner can always ignore the explanations, so noisy explanations never make learning harder than labels alone; how much of their benefit survives is open. The robust DFF algorithms you cite [2, 3] are a natural template, and Section 6 now states this limitation.

AuthorsOpenReview ↗

Reply to Reviewer EbuN(2/3)

W3 and Q2 (the explanation language; minimal or bounded-size explanations)

Thank you for pointing out the role of the explanation language. We agree that the benefit depends on it. In our model the language is the public rule set R, and β is measured on R. The revision addresses your three points.

Trivial explanations. We agree. If the whole input may serve as an explanation, every input becomes a rule, β is at least the VC dimension of the classifier class, and explanations give no saving, even under a fixed selection rule. Section 5.3 now states this.

A natural language with small β. New Proposition H.4 (summarized in Section 5.3) takes a public dictionary of N rules, such as the presence of features or substructures, and lets an input be positive when any of at most s ≤ N/2 unknown rules fires. Then β = s while the bag VC dimension is Θ(s log(N/s)), and explanations remove the log(N/s) factor for every selection rule, including history-dependent ones. This covers bounded-size explanations. If the rules are conjunctions of at most w literals over n features, O((s+log(1/δ))/ε) samples suffice against every provider, independently of n and w (Appendix H.4), because β counts the rules the target combines, not the length of an explanation. Since Ldim = s, this rate also follows from Theorem 5.1; the proposition adds a simple learner and the comparison with labels alone.

Minimal or bounded-size explanations (Q2). Yes, the separation persists, because our explanations are already minimal and of size one (new Proposition H.2). Encode an input by one Boolean feature per rule, so the target is the disjunction of its rules. Fixing one firing target rule to 1 is a sufficient reason, and an assignment that fixes none of them to 1 is not, because setting all free features to 0 gives a negative input. The minimal sufficient reasons (abductive explanations, prime implicants) are therefore exactly our valid explanations, and Theorem 4.1 and Corollary C.2 hold verbatim when providers must return minimal or size-one explanations. The provider's freedom lies in which of several minimal explanations it returns, the multiplicity you note in your related-work comment. Over raw features, minimal reasons need not be single rules, so we state the equivalence for rule indicators. If rules are conjunctions of at most w literals over n raw features, Proposition H.3(ii) caps the cost of history dependence at a factor O(w log n), so bounded size limits the separation without removing it (over rule indicators, 𝒢q_q has w = 1 and log n = Θ(q²)).

W4 (no characterization of the history-dependent rate)

Thank you for this suggestion; we agree that a characterization would strengthen the work. We do not have one, and Table 1's last column now reads "Dimension matching the rate on this family" to avoid suggesting otherwise. The paper asks whether the benefit of valid explanations survives history-dependent selection. Theorem 3.1 answers yes at β = 1 and Theorem 4.1 no in general, so the answer depends on the class and not on β alone. The causal rate lies between the memoryless rate, governed by β (Proposition 2.1), and the smaller of the Littlestone bound of Theorem 5.1 and the label-only rate. Any characterizing dimension must therefore lie between β and min{Ldim, v_bag}, be constant on every VC-one class even when Ldim is unbounded, and be Θ(q) on 𝒢q_q. The revision narrows the gap from both sides. There is no price at β = 1, and, with Ldim = β, none for subspaces, sparse rule dictionaries (Proposition H.4), and intersection-closed classes whose closure chains inside a target have at most β strict steps (Appendix H.4). Conversely, a gap of factor g requires inputs of size exponential in g (Proposition H.3). Beyond β = 1, all our harmless examples have Ldim = β, so they cannot tell whether the right quantity is closer to β or to Ldim. We consider this the main open problem raised by our results.

AuthorsOpenReview ↗

Reply to Reviewer EbuN(3/3)

W5 (the separating construction; the subspace rate)

Thank you for these two comments. We agree that 𝒢_q is a constructed family with very large inputs, as Section 6 notes. We should have made clearer that its masking is information-theoretic rather than cryptographic. Proposition 4.2 is an exact posterior identity, so the lower bound needs no computational assumption. Some exponential size is also unavoidable. New Proposition H.3 shows that on bags of at most b instances, history dependence costs at most a factor O(log(2b)) over the memoryless rate, so a gap of factor g requires bag and universe sizes exponential in g; our family uses exponent g², and whether the square is needed is open. We know of no natural provider that causes such a loss, and Section 6 now asks whether one exists. The negative result thus marks a boundary. Validity alone does not guarantee the memoryless rate, while a fixed selection rule always attains it, and in the natural sparse-rule setting of Proposition H.4 every selection rule does.

We also agree that the subspace rate follows from Theorem 5.1, since Ldim = d, and Section 5.2 now says so. Proposition 5.2 contributes an efficient proper learner that keeps a single span of at most nd field elements, with no enumeration and no majority vote.

W6 (accessibility to the interpretability audience)

Thank you for this comment; we agree that the original version was framed mainly for learning theory. The question comes from explanation practice. When explanations accompany training labels, how many labels do they save, and does it matter which valid explanation is shown? Over rule-indicator features, our explanations are exactly the minimal sufficient reasons, or abductive explanations, of the target (Proposition H.2). In these terms the results say three things.

  • A fixed criterion for choosing among valid explanations, such as the shortest, the first, or the most salient, is safe if it ignores earlier annotations. The labels needed then scale with the complexity of the rule set the explanations come from, not with that of the classifier (Proposition 2.1).
  • Validity alone is not enough in general. When several sufficient reasons are valid, an explainer whose choice depends on earlier annotations can withhold much of this saving, even if every explanation is minimal (Theorem 4.1, Proposition H.2). Such a cost requires a number of candidate rules exponential in its size (Proposition H.3), and we know of no natural explainer that causes it.
  • For a sparse dictionary of candidate rules, every choice is safe, and explanations remove a logarithmic dictionary-size factor from the labels needed (Proposition H.4).

To support this reading, the introduction's second paragraph now gives a feature example, in which the rules a = x₁∧x₂ and b = x₂∧x₃ both explain x = (1,1,1) but only b transfers to x' = (0,1,1). Section 2.1 maps it onto the model with a table, and the new related-work paragraph (W7) connects witnesses to abductive explanations.

W7 (related work)

Thank you for these references, which helped us position the paper. We added all of [1–9] in a new related-work paragraph (Section 1.2, in blue).

  • Discriminative feature feedback [1–3]. The teacher answers each mistake with a feature separating the current instance from an earlier one with a different label. These mistake bounds hold for every valid feature, hence for history-dependent teachers, but like our Theorem 5.1 they are online guarantees. We ask whether the smaller i.i.d., VC-type rate survives history-dependent selection; it does at β = 1, for subspaces and for sparse rules, but not in general (Theorem 4.1).
  • Sufficient reasons and abductive explanations [5–7]. We agree, and Proposition H.2 makes the correspondence exact over rule indicators. Their multiplicity, which you note is well studied, is exactly the provider's freedom; what we add is the cost of that freedom to a learner when the choice may depend on earlier examples.
  • Anchors [8] are sufficient with high probability rather than exactly, so they fall outside the current model, as noisy explanations do.
  • Proofs as Explanations [4] send certificates from the learner to the user, the opposite direction to ours.
  • Model reconstruction [9] exploits explanations that leak information about the model. Our lower-bound provider is the opposite case, since its valid explanations reveal nothing about unseen designated labels beyond the observed labels.

We hope these answers address your concerns, and we would be glad to clarify any point further.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response(1/2)

We thank the three reviewers for careful and constructive reviews, for recognizing the novelty of the setting (EbuN) and the precision of the question (PbxM), and Reviewer hK9q for computational checks of the β = 1 learner and the VC-two construction. Together, the reviews ask why we study guarantees that hold for every valid provider, whether the negative result depends on unnatural explanations or inputs, and what the results mean for explanation practice. We uploaded a revision with all changes in blue. It adds four short results in a new Appendix H, each derived from tools already in the paper, together with a worked feature example, the missing related work, and sharper statements of scope and limitations.

1. A cooperative provider cannot beat the memoryless order in the worst case (new Proposition H.1). Even if the provider is designed jointly with the learner and may use the target, the distribution and the history, the learner needs Ω((β+log(1/δ))/ε) samples. The hard distributions of Proposition 2.1 use only empty and singleton bags, on which every legal provider returns the same record. A fixed selection rule attains this order (for β > 2 via Montasser, 2026), so the memoryless rate is also the cooperative benchmark. On a particular distribution with several valid explanations, a helpful teacher can do better, and we do not characterize by how much. We agree that annotators are usually cooperative; the causal results measure what is lost when cooperation cannot be verified from valid explanations alone.

2. Minimal explanations leave every choice intact (new Proposition H.2). Encode a bag by its incidence vector, one Boolean feature per rule, so that the target becomes the monotone disjunction f_G(x) = ∨_{r∈G} x_r. At a positive input, the minimal sufficient reasons (prime implicants, abductive explanations) are exactly the one-literal reasons {x_r = 1} with r a legal witness. Requiring minimal or size-one explanations therefore leaves every provider choice intact, and Theorem 4.1 and Corollary C.2 persist. Over raw input features, minimal reasons need not be single rules, so we state the equivalence for rule indicators.

3. Every separation needs exponentially large inputs (new Proposition H.3). Ignoring witnesses and applying the multiple-instance bound (57) gives a causal numerator O(β log(2b)) on bags of at most b instances, and Theorem 5.1 with Sauer's lemma gives O(β log(e|R|/β)). For fixed β, a gap of factor g between the causal and memoryless rates therefore needs log b and log|R| of order at least g. Both ingredients were already in Appendix F.2, and H.3 states the consequence. Our family uses order g², and whether the square is needed is the open question of Section 6. With uniformly bounded bags, every class of finite latent VC dimension is causally learnable, so Corollary C.2 needs unbounded bag sizes, as Section 4 now states.

4. Sparse rule dictionaries pay nothing for history dependence (new Proposition H.4). Suppose an input is positive iff one of at most s ≤ N/2 unknown rules from a public dictionary of N rules fires. Then β = Ldim = s, while the bag VC dimension is Θ(s log(N/s)). The learner that predicts a bag positive exactly when it contains a witness returned on an earlier false negative attains Θ((s+log(1/δ))/ε) against every causal provider, versus Θ((s log(N/s)+log(1/δ))/ε) from labels alone. Since Ldim = s, the rate also follows from Theorem 5.1; the proposition gives a natural explanation language with a small latent dimension, a simple learner, and the comparison with labels alone. If the whole input may serve as an explanation, every input becomes a rule and there is no saving.

AuthorsOpenReview ↗

General response(2/2)

The revision thus gives the following picture.

  • History dependence is harmless at β = 1 (Theorem 3.1), for subspaces (Proposition 5.2) and for sparse rule dictionaries (Proposition H.4). In the last two, Ldim = β, so Theorem 5.1 already covers them; whether it is harmless for some family with β ≥ 2 and Ldim ≫ β is open.
  • For some families of latent VC dimension two it costs a factor q (Theorem 4.1), and a countable extension with unbounded bag sizes loses PAC learnability (Corollary C.2).
  • Any such cost requires inputs exponential in the size of the gap (Proposition H.3).

We agree with the following limitations, which the revision states.

  • The separating family is a constructed, information-theoretic example; its masking is exact and needs no cryptographic or computational assumption. We know of no natural history-dependent provider that is harmful, and Section 6 now asks whether one exists.
  • We do not characterize m⋆_cau, and Table 1's last column now reads "Dimension matching the rate on this family".
  • The rates of Propositions 5.2 and H.4 also follow from Theorem 5.1, because Ldim = β there; their contribution is simple, efficient learners.
  • Noisy explanations, and informative explanations of negative inputs under our OR semantics, are not covered (Section 6).
  • For β > 2, the optimal additive memoryless bound relies on Montasser (2026), and so does the matching order in Proposition H.1; the conclusion now says so. Theorems 3.1 and 4.1, Corollary C.2, and Propositions 5.2 and H.4 do not depend on it.

The main changes in the revised PDF, all in blue, are the following.

  • One added sentence at the end of the abstract, on sparse rule dictionaries and input size.
  • In the introduction, a worked feature example in the second paragraph, and a related-work paragraph on discriminative feature feedback, sufficient reasons and abductive explanations, Anchors, Proofs as Explanations, and model reconstruction.
  • In Section 2.1, the example mapped onto the model, with a correspondence table.
  • In Sections 4 and 5, remarks on minimal explanations (H.2), input size (H.3) and the unbounded bag sizes of Corollary C.2; the renamed column of Table 1; the detailed dimension arguments moved to Appendix C.2; the subspace rate via Theorem 5.1; small clarifications of the learners in Sections 5.1 and 5.2; and a new Section 5.3 on sparse rule dictionaries.
  • In Section 6, the caveat on Montasser (2026), the cooperative benchmark, negative and noisy explanations, and an open question on natural history-dependent providers.
  • In Appendix H, Propositions H.1–H.4 with proofs, and a few small precision edits in Appendices B–F.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.