acceptodds
Under review as a conference paper at ICLR 2027

Teaching and Learning under Deductive Errors

Abstract

Most models of machine teaching and learning assume the learner makes no errors in its internal deductive inference. However, humans and large language models in few-shot learning regimes are two important examples of learners where this does not hold. They fail on some consistency checks, and they can fail stochastically. In this paper we introduce a teaching and learning framework that takes these deductive errors into account. We specifically study the case of machine teaching, as different characterizations of the teacher can account for both machine teaching and learning. In an overhauled Probably Approximately Correct (PAC) setting, we study theoretically that, for some estimated error level, the teacher must find a PAC teaching set that with high probability will lead the learner to guess a hypothesis that is approximately correct. We study the computational complexity of six different problems related to computing optimal PAC teaching sets. We give XP algorithms parametrized by size of teaching set, with tight runtime bounds under standard complexity assumptions like ETH. These results are complemented with a small experimental study of which teaching and learning protocols can best represent the observed behavior in some LLM teaching sessions.

Primary area:
learning theory
Keywords:
machine teaching, deductive errors, teaching and learning franework, optimal teacher algorithms, computational complexity, tight runtime bounds

Reviews

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

In this paper, the authors consider a computational task, which is called the PAC teaching problem. In this setting, the learner does not learn a concept directly from the samples. Instead, there is an algorithm called a teacher, which picks the samples to train the learner to learn the concept and the set of samples picked by the teacher is called teaching set. The task this paper tries to handle is how to find an optimal teaching set. The main results is that finding such an opitmal teaching set is hard under ETH. There are some hardness results in the parameterized complexity class as well.

Critical strengths

This paper considers the computational hardness of the teaching problem, especially when the learner may not always be consistent with the learned function. It is an interesting theoretical framework.

Critical weaknesses

I do not see many interesting technical ingredients in this paper. I also do not see the importance of this problem. The presentation of this paper makes it very hard to follow. First, what is the main problem this paper is trying to address? This is very unclear until the very end of this paper. Second, it spends a lot of words distinguishing the notion of teaching for identification and teaching for employment. But this distinction does not show up in the final theorem. I think the author should focus on the main definitions that are closely relevant to the main results and put the less relevant notations after the main results.

Questions for authors

In short, what is the main motivation of this research? Is it the question of computational efficiency in finding an optimal teaching set when the learner has pointwise noise in its predictions?

How untraditional is the reduction in this paper? Is it an easy implication of some traditional reductions?

3 comments

The reviewer writes: 'The main results is that finding such an opitmal teaching set is hard under ETH.'. This must be based on a very cursory reading of the paper. We are very clear that the main contribution is the 'introduction of the PAC teaching framework, that is useful whenever we have a learner who does not perform perfect deductive inference'. This is an important contribution to the field, but I guess we must take responsibility for not having shown why this is important. We will add examples in the revision. PS Very disappointing that ICLR assigns our paper to a reviewer with no direct research experience in learning theory.

I sincerely do not see a significant difference between the model proposed by the author in this paper and the existing active learning with label noise model. I really want to understand what the difference between those models and what part changed in the result. I would appreciate the author if they can state this and make a good comparison to all the existing models. I apologize if I do not make this point clear in my initial comments.

According to the main theorem of this paper, I think the authors consider the computational resources required by a specific type of learning algorithm, which is very different from a normal statistical learning theory paper. They call this learning algorithm the PAC teaching model. Thus, I wrote the following sentences in the paper summary.

In this setting, the learner does not learn a concept directly from the samples. Instead, there is an algorithm called a teacher, which picks the samples to train the learner to learn the concept and the set of samples picked by the teacher is called teaching set.

What the author wrote in their paper:

Informally, in PAC teaching, when using a good teaching set S for the target concept c∗c^{\ast}, it should be probable that the concept c chosen by the learner (e.g., the concept that is L-consistent with most labelled examples in SS), is approximately equal to the target c∗c^{\ast}. Finally, we introduce the Prudent-optimal PAC teacher TP aiming to find an optimal teaching set SS.

And in the theorem

Theorem 1. The problem facing the Prudent-optimal PAC Teacher TP for probable-optimizing (id or em), given consistency matrix C×XC × X and γL\gamma_L, approx factor qq and max-size kk, for a given target, can be solved in time O(k3∣C∣∣X∣k)O(k^3|C||X|^k).

The problem facing the Prudent-optimal PAC teacher TP, (I think this should be "the problem faced by the teacher"?) is the problem to find the optimal teaching set SS, as in the part cited above. I am not sure what the problem is in my interpretation of this theorem. I am very happy to know if there are some.

In my opinion, this paper is about computational hardness of a learning problem with label noise, or maybe more specifically, the computation complexity of the following problem: An algorithm with instance space and target concept and concept class in hand, want to pick a set of unlabeled data, then use a coin to decide the label for each unlabeled datum (the label noise), then what is the computation complexity of this problem? The model in this work seems very similar to the active learning under label noise to me. The learning under noise model has been extensively investigated in the area of statistical learning theory, both passive and active and I believe it is also investigated in computational learning theory.

However, I feel that the author's response is offensive and inappropriate, especially the assertion on the research experience of the reviewer. It is unclear what supports the author's assertion that the reviewer has no direct research experience in learning theory. I am happy to know the reason why the authors make such an assertion. I would like to say that learning theory is a large research area, people has considered learning problem from very different perspectives and I would not exclude other subareas from learning theory only because they are using different language or caring about different aspects.

Thank you for the follow-up.

Active learning: We have a teacher-learner setting, and the teacher has an algorithm to choose the examples. This is standard in the field of machine teaching, from the early days of learning theory, where machine teaching and query learning (and active learning) diverged. Precisely, in machine teaching, the teacher knows the concept, and the algorithm works with that information. In active learning, it is the learner asking for the examples. The learner doesn't know the concept of course, so the algorithm uses the learner's uncertainty to pick the next examples but can't use any information about the target concept. So it's not only that the example-selection algorithms are on different sides of the teacher-learner setting, they must be fundamentally different.

Label noise: Even assuming that the teacher samples according to a distribution (and then machine learning becomes a special case of machine teaching), labelling errors are fundamentally different from learner errors. Using the same example we used with another reviewer, when we consider a non-deterministic target and a perfect learner, the noise is in the label of the example. The learner sees one label and checks all its hypotheses against that label. In our model, the label is always correct and the noise is in the learner’s checks. Each time the learner checks whether a hypothesis is consistent with an example, it can make a mistake. With two hypotheses, both models can give the same result, and that's maybe why it is difficult to see. However, in general, with three or more hypotheses, they can give different results. Two hypotheses. The target is “multiples of 3”. The positive examples are 15, 45, 105 and 219, and the negative examples are 8 and 10. Suppose the label of 219 is wrong 50% of the time. A learner that makes no mistakes will select “multiples of 15” 50% of the time and “multiples of 3” 50% of the time. Now suppose the labels are always correct, but the learner makes a mistake when checking 219 50% of the time. The result is again 50% for each hypothesis. Modelling this either way would give equivalent results. Three hypotheses. The target is again “multiples of 3”. The positive examples are 3, 9 and 15, and the negative examples are 4, 10 and 91 (which may look like a multiple of 3). The learner tries the hypotheses in the following order and selects the first consistent one: (1) odd numbers, (2) multiples of 3, (3) odd numbers below 30. With no errors, (1) is rejected because of 91, and (2) is selected. Noisy label: 91 is labelled positive 50% of the time. When this happens, (1) is consistent with all the examples. Result: (1) 50%, (2) 50%. Learner error: the labels are correct, but 50% of the time the learner thinks 91 is a multiple of 3. (1) is always rejected, since the label of 91 is correct and checking that 91 is odd is easy. (2) is rejected 50% of the time, and then (3) is selected. Result: (2) 50%, (3) 50%. The two ways of "modelling" this are not only conceptually different but they give different results. Modelling this as labelling errors cannot account for the situations we consider in this paper. We can add this example to an appendix.

Learning theory vs computational complexity: Our comment referred to the fact of seeing a strong reject with low confidence and a comment about ETH, leading us to believe the reviewer came mostly from computational complexity, when we selected "learning theory" as the topic of our paper. We apologise if this is not the case. We can understand a strong reject when the gist of the paper is understood and it contains major errors or doesn't add anything novel or useful. We honestly think this is not the case for this paper.

Reviewer_h7onOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

The paper presents a new formal framework that is a variation of "teaching", where a teacher model picks optimal sets of examples for a learner model, where the learner is assumed to make random errors in some of its inferences. There are also experiments with teaching heuristics on a family of arithmetically defined classification tasks.

Critical strengths
  • The paper is clearly written and upfront about its limited scope.
  • The paper seems to have been written by a fellow human being, which is appreciated!
Critical weaknesses
  • The leading claim that "Most models of machine teaching and learning assume the learner makes no errors in its internal deductive inference" ignores the existence of the vast amount of ML in which hypotheses are probabilistic.
  • The experiments are extremely limited, and the results of Figure 1 (a,b) are extremely unsurprising.
  • PAC-Teaching in the classic Goldman/Kearns sense seems a poor match for the scale of 1-2 examples.
  • There are previous relevant works that are not discussed, eg https://arxiv.org/abs/1111.1422
Questions for authors
  • Does the noisy-LLM-learner insight translate to concrete gains on any realistic tasks?
3 comments

The reviewer writes: 'The leading claim that "Most models of machine teaching and learning assume the learner makes no errors in its internal deductive inference" ignores the existence of the vast amount of ML in which hypotheses are probabilistic... There are previous relevant works that are not discussed, eg https://arxiv.org/abs/1111.1422".

There is a fundamental distinction between probabilistic hypotheses as discussed e.g. in that arxiv paper and the study of deductive errors we introduce in our paper. In that arxiv paper (Robust Interactive Learning - Balcan and Hanneke, 2011), the learner can evaluate hypotheses correctly, but the data need not agree with any hypothesis perfectly. In our paper, the teaching data are correctly labelled according to a target concept, but the learner can incorrectly calculate what a candidate concept predicts. This is not simply a difference between two noise rates: the noise enters at a different point in the learning process.

Studying deductive errors matters because learning the right rule and reliably applying that rule are different capabilities. A human or LLM may identify the intended concept yet misapply it, or reject it during learning because it incorrectly computes its consequences. More accurate labels alone cannot fix this. Accounting for deductive errors therefore changes which interventions are useful: examples must be not only informative but also reliably interpretable by the learner; verification or computational assistance may matter as much as additional training data.

These errors are not subsumed by probabilistic hypotheses. There, each example has one observed label, and every candidate hypothesis is evaluated exactly against it. Consequently, two hypotheses that predict the same label on an example must receive the same consistency judgment. With deductive errors, the learner can evaluate those hypotheses differently—for instance, because their representations require different computations—even though their correct predictions agree. No single corrupted label can reproduce that behavior.

The distinction is therefore structural, not merely terminological: the first model allows unreliable evidence relative to the hypothesis class; the second allows unreliable processing of evidence, even when the evidence is perfect. Some special cases can be represented as label noise, but the general phenomenon requires a richer model.

I still don't see why this case isn't correctly modeled by a hypothesis class of non-deterministic target functions.

Thank you for the follow-up. We think an example would make the difference clearer.

With a non-deterministic target and a perfect learner, the noise is in the label of the example. The learner sees one label and checks all its hypotheses against that label. In our model, the label is always correct and the noise is in the learner’s checks. Each time the learner checks whether a hypothesis is consistent with an example, it can make a mistake.

With two hypotheses, both models can give the same result, and that's maybe why it is difficult to see. However, in general, with three or more hypotheses, they can give different results.

Two hypotheses. The target is “multiples of 3”. The positive examples are 15, 45, 105 and 219, and the negative examples are 8 and 10. Suppose the label of 219 is wrong 50% of the time. A learner that makes no mistakes will select “multiples of 15” 50% of the time and “multiples of 3” 50% of the time. Now suppose the labels are always correct, but the learner makes a mistake when checking 219 50% of the time. The result is again 50% for each hypothesis. Modelling this either way would give equivalent results.

Three hypotheses. The target is again “multiples of 3”. The positive examples are 3, 9 and 15, and the negative examples are 4, 10 and 91 (which may look like a multiple of 3). The learner tries the hypotheses in the following order and selects the first consistent one: (1) odd numbers, (2) multiples of 3, (3) odd numbers below 30. With no errors, (1) is rejected because of 91, and (2) is selected.

Noisy label: 91 is labelled positive 50% of the time. When this happens, (1) is consistent with all the examples. Result: (1) 50%, (2) 50%. Learner error: the labels are correct, but 50% of the time the learner thinks 91 is a multiple of 3. (1) is always rejected, since the label of 91 is correct and checking that 91 is odd is easy. (2) is rejected 50% of the time, and then (3) is selected. Result: (2) 50%, (3) 50%.

The two ways of "modelling" this are not only conceptually different but they give different results.

Now, can a non-deterministic target give the second result? No. Hypotheses (2) and (3) give the same label on all six examples. So whatever labels the learner sees, (2) and (3) are either both consistent or both inconsistent. Since the learner tries (2) first, it can never select (3). Adding noise to the labels, on any of the examples, does not change this. Only an error in the learner’s checks can lead to (3).

So a non-deterministic target can reproduce some cases of deductive error, like the two-hypothesis case, but not all of them.

This also matters for understanding teaching when you assume the learner can make mistakes on difficult examples. In our model, 91 is a bad example even though its label is correct, because the learner may process it wrongly. A teacher should choose an easier negative example, such as 5.

Reviewer_5E7MOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces a machine-teaching model in which a learner can misjudge whether a correctly labelled example agrees with a candidate concept. A teacher chooses examples for a learner that selects the concept with the most perceived agreements, with independent error probabilities depending on the concept and example. The objectives distinguish identifying an approximately correct concept from selecting one the learner can execute reliably. The authors derive an exact success-probability calculation, use it in exhaustive algorithms for six optimization problems, and establish complexity bounds. An illustrative GPT-5-nano study examines associations between deductive difficulty and teaching error and evaluates two example-selection heuristics.

Critical strengths
  • Locating errors in the learner's evaluation of a rule gives the teacher information that truthful labels alone do not provide. Two examples can distinguish the same hypotheses while differing in how reliably this learner can evaluate them, as the worked example in Section 4 illustrates. Allowing errors to depend on both the concept and example captures this difference and makes the reliability of a proposed explanation an explicit teaching consideration.

  • The exact probability calculation makes candidate teaching sets assessable without enumerating every possible pattern of deductive errors. By computing the distribution of perceived agreements for each concept and comparing the best acceptable and unacceptable scores, it evaluates a set in polynomial time. The conservative treatment of ties gives a guarantee that does not depend on choosing a favorable tie-breaking rule. This provides a basis for exact optimization on small finite instances and for checking proposed teaching strategies against the specified learner.

  • The distinction between identification and employment captures a failure that identifying the correct rule alone cannot address: the learner may still apply that rule unreliably. An employment objective lets the teacher account for subsequent execution, including the possibility that an approximate concept yields more accurate actions than the exact target. This matters for the paper's motivating use of teaching as an explanation that a person or model must subsequently apply.

Critical weaknesses
  • The paper gives limited guidance on when accounting for deductive errors changes how we should teach. The worked example favors easier checks when examples are equally informative, but does not explain how to balance ease of evaluation against informativeness. Similarly, distinguishing identification from reliable application is useful, but its effect on a teaching decision is not developed. A concrete example of these trade-offs would help explain what the formulation adds.

  • The higher error in the paired-example setting does not clearly establish greater inductive difficulty. This setting also changes the example pool and adds a negative condition to the prompt, either of which could affect performance. Moreover, errors measured through isolated binary questions may differ from those made when choosing among concepts. The results show an association between deductive and teaching difficulty, but the proposed explanation needs stronger support.

  • The heuristic experiments do not isolate the benefit of estimating deductive errors. Selected examples often have low teaching error, but there is no comparison with a selector that ignores these estimates under the same example pool and teaching budget. Such a baseline would show whether the estimates improve example selection beyond choosing simple, logically sufficient examples.

  • Some reported examples do not match the stated teaching protocol. Under the stated single-positive-example protocol, Table 1 selects 305 for target 11 and reports zero teaching error, although 305 is not divisible by 11. The pairs in Table 2 also appear to require the reverse of the stated label order. These may be reporting issues, but the actual labels and correctness criteria need clarification before the results can be interpreted reliably.

Questions for authors
  1. Can you give a concrete case where accounting for deductive errors, or distinguishing identification from reliable application, changes the preferred teaching decision?
  2. What supports attributing the paired-example result to inductive difficulty, given the changes in examples and prompt structure?
  3. What labels and correctness criteria were used for the examples in Tables 1 and 2?
1 comment

The reviewer has 3 concrete questions, We address them in order. Question 1.Can you give a concrete case where accounting for deductive errors, or distinguishing identification from reliable application, changes the preferred teaching decision? Sorry if this was not clear, but yes we can. For example, the paragraph in the middle of page 6 starting 'Let us illustrate the benefits of PAC teaching with a very simple case highlighting the difference between the naive learner with a naive teacher versus the prudent learner with a heuristic teacher'. Also, on line 382, page 12, referring to Figure 2 (left), we write: 'Both heuristics select a teaching set x of very low total teaching error of at most 0.02, for all 5 values of k, showing their usefulness in this case.' Looking at Figure 2, a value on the y-axis of 0.02 is clearly very low. Question 2: What supports attributing the paired-example result to inductive difficulty, given the changes in examples and prompt structure? Your point is well-taken, and in lines 159-164 we discuss this and explain why we call it Total Teaching Error rather than Inductive+Deductive Error precisely because of this point. So our argument does not rest on whether these are inductive difficulties or other difficulties. Question 3: What labels and correctness criteria were used for the examples in Tables 1 and 2? We are sorry if this was not clear. Let us construct the binary consistency matrix. We have the set of concepts C='multiples-of-k' where k is one of the five numbers 5,7,11,13,17. We have examples X={1,2,...,1000}. For concept c_11 (say 'multiples-of-11') the example x (a number, say 33) has a binary label c(x) stating whether x is a multiple of 11 (label 1) or not (label 0). For teaching we only use the subset X' of X consisting of numbers x that have c_k(x)=1 for a single c_k (say k=11) and c_p(x)=0 for all others. This is explained in lines 177-196 and we did not have space to repeat it when presenting Table 1. Sorry for that. And also we apologize for the two mistakes in Table 1, both the 305 in row 11 and the 132 in row 13 are wrong. There seems to have been a bug in the code extracting the results from the evaluations into the papers as seen in the CSV file: PAC_teaching/Results/heuristic_scores_1td.csv at main · BrigtHaavardstun/PAC_teaching · GitHub. This will be fixed in later versions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.