PAC Learning with Improvements

“why should the hypothesis be penalized at point despite being correct there and offering at least 1 valid improvement option?”

Thank you for your question.
Let's consider a motivating scenario: suppose that in order to do well in your research group, an applicant needs to (a) know basic concepts from probability and (b) be able to apply them. A test $h$ that only tested knowledge of definitions would not be a good test because an applicant $x$ might then only study the definitions and move to point $z_2$, rather than studying the definitions and practicing solving problems with them, moving to point $z_1$. In general, our definition assumes that if agents are able to move to a point $z$ where $h(z)=1$ but $f^*(z)=0$, then they will do so, under the theory that if you're not sure, it's better to assume the worst. Note that this makes our positive results stronger than assuming any specific tie-breaking behavior.

Another perspective on this modeling is as follows. Imagine that we want to grant a loan to an agent. If h decides that the agent can improve to qualify for the loan, then from the agent's perspective, they will indeed receive the loan (as they are only affected by $h$'s decision). However, it is possible that the policymaker (h) makes a mistake—this agent may not actually be able to improve with respect to $f^∗$. Our loss function is the most restrictive for the policymaker, as it encourages h to make conservative decisions, but from the agent’s perspective, “what they see is what they get.”

Furthermore, we would like to point out that prior work on strategic classification (where agents move to deceive the classifier instead of genuinely improving) also makes the same assumption that an agent moves to the positive point that maximizes the learner’s loss whenever it can do so (cf. Sundaram et al., 2023: “When there are multiple best responses, we assume the data point may choose any best response and thus will adopt the standard worst-case analysis.”). We agree that a specific tie-breaking behavior could capture different modeling aspects of the problem.

“.., is the closure algorithm always a valid PAC learner, although it becomes improper when the hypothesis class is not intersection-closed?”

This is a great question. The answer is no. This is implied by Example 2 (the hypothesis class is indeed not intersection-closed here), where the VC dimension is finite, but our argument rules out the existence of any PAC learner (proper or improper, including the closure algorithm) for the problem with access to finitely many samples.

“A more thorough comparison with the adversarial robustness literature.”

Thank you for the helpful suggestion. We will make sure to include the distinction between our setting and the adversarial robustness literature and the following points of comparison:

• Finite VC dimension is not sufficient for PAC learnability with improvements (Example 2) as opposed to adversarial robustness, where it is sufficient for (improper) learning. This is a major difference between the models. On the other hand, infinite VC dimension does not rule out learnability in both models (Example 1 and MHS2019).
• In adversarial robustness, the learner's error can only increase compared to the case where there is no adversary. In PAC learning with improvements, this is not necessarily the case, and we present several examples where the error is smaller than in standard PAC learning.
• Modeling differences: While in adversarial robustness the role of the labels 0/1 is similar (the adversary simply tries to force a misclassification), in our setting, there is an asymmetry between the labels: the agent won’t even react if it is classified as 1. Another point of distinction is that, as you mentioned, the robustness set is predefined and independent of the deployed hypothesis, whereas in our setting, the reaction set is a function of the hypothesis itself.

In general, we are very familiar with the techniques in the adversarial robustness literature and have even tried to employ some of them, but it seems that the two models behave quite differently due to the above differences. For example, our risk-averse algorithm is very different from the robust-ERM approaches in the adversarial literature [Cullina et al., 2018] and sample compression scheme algorithms [Montasser et al. 2019, Attias et al. 2023].
Our results indicate that the properties of H that govern learnability (or the characterizing dimension) should be different for the two models. However, due to analogies between the frameworks, it is meaningful to ask future research questions along the lines of the directions pursued in the adversarial robustness literature e.g. extensions to unknown or uncertain improvement sets (cf. [Montasser et al. 2021, Lechner et al. 2023]). Any suggestions are welcome.

We will add the above discussion in our revision. We are happy to answer and clarify any further questions.

We thank the reviewer for their constructive comments and very interesting questions which inspire directions for promising future research.

“The threshold/half space examples have vague similarities with learning with margin (or perhaps a one-sided version of it). Is there any relationship between the setting here and learning margin halfspaces or partial concept classes in general?”

Thank you for the question. Our results indicate that risk-averse learners work well across different concept classes. Specifically, learners that output the positive agreement region $f_+$ of the labeled sample, i.e. the function that classifies the intersection of the positive region of classifiers consistent with the data, achieves low error in our setting. For learning halfspaces, this function may not be a halfspace and if we are restricted to proper learning, the learner may output a halfspace $h_+$ with sufficient margin to positively classify only a subset of the positive agreement region. This would involve sacrificing some accuracy, unless the data is separable by a large-margin classifier (margin large enough relative to the agent's ability to move) such that there is no probability mass between $f_+$ and $h_+$. In other words, when learning on separable data with a sufficiently large margin, our setting would coincide with the standard setting, but not in general (there may be some loss in accuracy).

“Is there some natural (sufficient) requirement on $\Delta$ (and/or $H$ and the used learning algorithm as in Theorem 4.7) such that finite VC is sufficient for learning here? Perhaps some sort of monotonicity or smoothness?”

The intersection-closed property is an example of a sufficient requirement on $H$, such that for an arbitrary $\Delta$ finite VC dimension is sufficient for learning. There might be weaker properties that are sufficient for some restricted classes of $\Delta$ such that the above property holds. As an extreme case on the other hand, if we make no other assumption on $H$, then $\Delta(x)=\{x\}$ is an example where a finite VC dimension is sufficient, as this reduces to the standard PAC learning setting. Examining intermediate cases, involving some combination of sufficient natural assumptions on $\Delta$ and $H$, is an interesting and natural question for further research.

Not important comment: Note that what you call "non-realizable"...

We agree that the terminology in this context might be confusing and that it could be improved. Thanks for pointing it out. We changed this paragraph to the following: “As another example of the distinction between our model and the standard PAC setting, consider the following example. We construct a distribution D that is realizable by the class H, yet the target function $f^*$ does not belong to H. That is, there exists h in H with zero error on D, but h differs from the ground truth $f^*$. However, in our PAC learning model with improvement, the best function h in H must incur an error of $1/2$​ for the same ground truth function $f^*$.” We will also change the terminology in the proof (Example 3 in the appendix).”

On the different problems considered and the overarching picture

As the reviewer notes, the overall picture is quite complex, and our problems capture different aspects of it. For proper learnability (when the learner must output a hypothesis from a fixed set H), the intersection-closed property is sufficient and essentially necessary. Our halfspaces example shows that if the intersection-closed property is not satisfied, there is still hope to learn using improper learners. The graph model captures that if we can reasonably express (say by some discretization) the instance space X and the improvement function $\Delta$ using a graph, then for any H we can achieve learning with zero-error given enough samples (that depend on the graph and target concept $f^*$).

We will incorporate the above discussions and clarifications in our revised version. Additionally, we will also add a remark that our graph model is related to manipulation graphs previously studied under strategic classification; the difference being here the edges correspond to potential true improvement instead of “admissible feature manipulations”. We would be happy to answer and clarify any further questions.

We thank the reviewer for appreciating our work, and for the insightful questions and suggestions.

Relationship between FP weight and imbalance

At this moment, we cannot confirm a specific relationship. However, the choice of false positive and false negative weights required to train a positive reliable classifier is affected more by class separability than by class imbalance. Specifically, when a dataset exhibits strong class separability, we may not need to impose an aggressive false positive-to-false negative weight ratio to achieve a positively reliable (risk-averse) classifier, as discussed in our paper.

Intuition on behavior when $w_{FP}$ is increased and why the error consistently larger

Increasing the ratio $w_{FP}/w_{FN}$​ (e.g., $4.0/0.001$) causes the model to penalize false positive mistakes more heavily, prioritizing their reduction at the cost of increased false negatives compared to when $w_{FP}/w_{FN} = 1$ (i.e., a BCE-trained model). Consequently, across all datasets, the initial error at $r = 0$ (before any agent improves) is higher than that of the BCE model. However, as agents improve, the false negatives decrease. We will also include more evaluation results to provide more intuition on how agents' movement impacts the resultant TPs and FPs.

``What does a small improvement budget in section 6 correspond to? What does $r=2$ mean? At which point are all $x$ able to obtain a positive label?''

Agents improve within an $\ell_{\infty}$ ball of radius $r$ (lines 417–435). A smaller improvement budget restricts agent movement to a smaller radius. The point at which all $x$ agents can receive a positive label depends on dataset separability, the risk aversion (e.g., weighted BCE loss-trained model), and the radius of the improvement ball.

Connection of the experiments to the theoretical results.

Thank you for pointing this out. We will include the following paragraph at the beginning of the evaluation section to better connect its motivation to the theoretical discussion: "This section empirically examines various improvement-aware algorithms, specifically practical risk-aversion strategies (loss-based and threshold-based) since risk-averse classifiers perform best according to our theory, which consider agents improving within a limited improvement budget $r$. We also explore whether and under what conditions the model error can be reduced to zero when negatively classified agents can improve within an $\ell_{\infty}$ ball of radius $r$. Recall that zero-error is a remarkable property achievable in the learning with improvements setting, even for fairly general concepts (cf. Section 5 where the instance space is discrete but the concepts can be arbitrary functions).”

.., it might be useful to relate this more clearly to existing work such as strategic classification.

Thank you for the helpful suggestion. While we already include a discussion of how our work compares with existing work on strategic classification, we agree that it is very useful to establish a clearer connection. Note that in strategic classification, the agents move in order to deceive the learner, while in our setting they try to truly improve. This subtle difference in the definition results in very different characteristics of learnability under the two settings. In particular, there are instances where learning with improvements is more challenging than strategic classification and vice versa.

Concretely, prior work by Sundaram et al. (2023) shows that a bounded “strategic VC” dimension is sufficient for learnability in strategic classification. This is however not true for our setting. It is possible to construct a concrete instance along the lines of Example 2, where the strategic VC dimension is constant but no learner (proper or improper) can achieve learnability with improvements. On the other hand, learnability with improvements can in some cases be easier than strategic classification. For example, consider the setting where the agents can move anywhere and the concept class consists of classifiers that label exactly one point in X as positive, plus the classifier that labels every point negative. Suppose the target $f^*$ and data distribution $D$ are such that $Pr_D[f^*(x)=0]=Pr_D[f^*(x)=1]=\frac{1}{2}$. Given $\log 1/\delta$ samples, the learner sees at least one positive point with high probability. Now the learner can output the hypothesis that only labels this positive point in the sample as positive and achieve zero error in learning with improvements (all agents will move to this point). But in strategic classification any classifier suffers error at least $\frac{1}{2}$ (if any point is classified positive, all negative points will successfully deceive; else all positive points are classified incorrectly).

We will add the above examples that establish a separation between our model and strategic classification to clarify the comparison with the strategic classification model.

We thank the reviewer for taking the time to review our work. Below are responses to the questions they raised.

Terminology - “hypothesis class”[H] vs. “concept class” [C]

We indeed make the common assumption of implicitly taking H=C. While earlier papers in the field considered the case where a hypothesis class H is used to learn a concept class C (aiming to compete with the optimal hypothesis in H), we can always take H=C, which is particularly natural in the realizable setting—our main focus in the paper. That's why we use these terms interchangeably. We will clarify this terminology in our revised version but emphasize that all statements are correct as they are, without any changes. See, for example, Def 3.1 of PAC Learning in “Understanding Machine Learning: From Theory to Algorithms” [1]. A recent example is [2] (see e.g. Pg 2 or Pg 20) or see [3] for an example from earlier literature (first sentence says most work assumes H=C).

[1] Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.

[2] Alon, Noga, Steve Hanneke, Ron Holzman, and Shay Moran. "A theory of PAC learnability of partial concept classes." In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 658-671. IEEE, 2022.

[3] Kobayashi, Satoshi, and Takashi Yokomori. "On approximately identifying concept classes in the limit." In International Workshop on Algorithmic Learning Theory, pp. 298-312. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995.

To be clear, when we say that a distribution D is realizable by a hypothesis/concept class H, we mean that there exists h in H with zero error on the distribution D (see, for example, Def 2.1 in “Understanding Machine Learning: From Theory to Algorithms”). When we say an “improper learning algorithm,” we mean that the algorithm can output any function while competing with the best hypothesis in H.

“hypotheses" outside of the "hypothesis class" (page 2, footnote 1)”

Actually, we wrote, “An improper learner can output any function h : X → {0, 1} that may not be in H.” We will update the variable name $h: X \rightarrow \\{0,1\\}$ to $f: X \rightarrow \\{0,1\\}$ for clarity. This is consistent with the definition of improper learning, see, for example, Remark 3.2 in “Understanding Machine Learning: From Theory to Algorithms”.

“they allow on one hand hypotheses to be outside of the hypothesis class and apparently now they also allow target concept functions (ground truth functions) to be outside of the hypothesis class as well!!”

We agree that the terminology in this context might be confusing and that it could be improved. Thanks for pointing it out. We changed this paragraph to the following: “As another example of the distinction between our model and the standard PAC setting, consider the following example. We construct a distribution D that is realizable by the class H, yet the target function f^* does not belong to H. That is, there exists h in H with zero error on D (in the standard PAC model), but h differs from the ground truth f^. However, in our PAC learning model with improvement, the best function h in H must incur an error of 1/2​ for the same ground truth function f^.” We will also change the terminology in the proof (Example 3 in the appendix). We believe this terminology is easier to understand, but we emphasize that the statement is already correct as it is, without any further changes.

We would be happy to answer and clarify any further questions.