Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning

We thank the reviewer for their comments and helpful suggestions (which we intend to incorporate in our revision), and address their questions and concerns below.

1. Theorem 3.4 seems to be a qualitative characterization of proper learning with improvements. Is there a quantitative characterization? That is, what is the optimal sample complexity for learning with improvements? Is there a dimension that characterizes this?

Yes, the proof of Theorem 3.4 in Appendix B gives a quantitative characterization. The sample complexity is governed by the (vanilla) VC-dimension when the concept class is learnable at all with improvements. Specifically, when $\mathcal{H}$ is nearly minimally consistent, the sample complexity is that same as that of vanilla PAC-learning: $O(\frac{1}{\varepsilon} (d_\text{VC}(\mathcal{H}) + \log \frac{1}{\delta}))$ under the realizability assumption (see bottom of page 14), and this is tight because the same lower bond argument for vanilla PAC-learning also serves as a lower bound for learning with improvements (take the closure of the concept class to make it minimally consistent). On the other hand, when the concept class is not minimally consistent, the proof of Theorem 3.4 constructs an improvement function $\Delta$ (recall that the definition of learnability in Section 3 is respect to every improvement function) and a distribution $\mathcal{D}$ for which any learner (even computationally unbounded) suffers constant error, so the sample complexity is unbounded. (In particular, a concept class could have small VC-dimension and thus small vanilla sample complexity but if it is not nearly minimally consistent it is guaranteed to have unbounded sample complexity in the improvements model.) To summarize, while VC-dimension is not sufficient to guarantee learnability with improvements, when the concept class is nearly minimally consistent, the sample complexity is governed by the VC-dimension.

2. Perhaps I'm mistaken, but when learning with label-noise, the goal is still to obtain small population error with respect to the true labels (not the noisy labels). It's just that the labels in the training data are noisy. This makes me confused about the noisy loss function defined in Line 274. Why is the loss here in terms of the noisy labels? What does getting a loss of $1$ here mean?

Great question. While it seems sensible to define the loss in terms of the true labels, the standard literature on bounded noise (e.g. Balcan and Haghtalab [2020], Diakonikolas et al. [2019]) define error as the expected loss of the classifier over the joint (noisy) distribution $\mathcal{D}$ over $X\times Y$, and the goal is to compete with the Bayes optimal classifier which predicts the most likely label for each point (the bounded noise is assumed to be less than $\frac12$ so this matches the “true” label without noise) and whose expected error is given by "OPT" (which is no more than the noise upper bound $\nu$). The guarantees in standard PAC learning with noise (i.e. with improving or strategic agents) are usually stated in terms of excess expected error over “OPT" in terms of a loss function that includes an expectation over the noise. Specifically in our setting, in addition to following the standard PAC learning convention, we choose the expected loss as it has the following nice interpretation. In the noisy setting, whether an agent is truly qualified given features $x'$ is a random variable (as opposed to a deterministic function $f^* (x)$ in the noiseless setting), and we want our predictions to be accurate (even as the agents move) in expectation. A loss of $1$ means that there is some point $x’$ to which the agent can “improve” to (if negative, the agent stays put if $h(x)=1$) such that our prediction $h(x)$ is completely inaccurate (almost surely).

3. In Lines 193-194, are you claiming that proper learning is without loss of generality if $\Delta$ can be anything? Are you claiming that there exists a choice of $\Delta$ such that a class $H$ is improperly learnable with improvements if and only if it is nearly minimally consistent?

Here is a clearer wording of that paragraph that we just edited based on your feedback:

We first note that in order to get interesting results, we must make some assumption on the improvement function $\Delta$. This is because we show that any concept class that is improperly PAC-learnable for all $\Delta$ must also be properly PAC-learnable, and we have already characterized proper PAC-learnability in Section 3 using the nearly minimally consistent property. (Recall that proper learnability trivially implies improper learnability.) Indeed, if $\Delta(x) = \mathcal{X}$ for all $x\in \mathcal{X}$ then the learning algorithm cannot make any false positives or else every negative instance can "improve" to such a false positive and incur a classification error. On the other hand, if $\Delta(x) = \\{x\\}$ for all $x\in \mathcal{X}$ then the learning algorithm cannot incur too many false negatives as any false negative is unable to improve. These two examples show that if we make no assumption on $\Delta$, the concept class must be learnable with one-sided error, which implies that it is properly PAC-learnable by our results in Section 3.

4. The algorithms for online learning are deterministic. While this is fine in the realizable setting, in the agnostic setting, randomization is key to removing the multiplicative factor in front of OPT. Is there a natural way to randomize Algorithm 3 and remove the $\Delta$ factor in front of OPT? If not, what is the barrier?

We believe that it is indeed possible to give a randomized algorithm which achieves sub-linear regret (as opposed to $\Delta_G \cdot \text{OPT}$ mistakes). One way to do this is to use a modified version of the Hedge algorithm (or EXP3 under bandit feedback) where we update the weights after $K$ rounds and use the all-negative classifier on one of every $K$ rounds (chosen uniformly randomly). This would be a conservative version of Algorithm 3 of Ahmadi et al. (2023), a difference being they use the all-positive classifier instead to incentivize the agent to not make a deceptive move (while we use a conservative all-negative classifier to keep the agent from trying to improve).

I thank the authors for their response. Looking at the proof of Theorem 3.4 and the authors reply to my first question, it seems like you require the class H to also have finite VC dimension. However, the fact that H needs to have finite VC dimension is not stated in Theorem 3.4. Can the author's clarify this? Should the correct characterization of proper PAC-learnable with improvements be:

"A class H is properly PAC-learnable with improvements if and only if H has finite VC dimension and is nearly minimally consistent"?

If so, your proof of the necessity of finite VC dimension in your reply to Question 1 should be included in the paper and the statement of Theorem 3.4 needs to be updated accordingly.

We thank the reviewer for their comments and address their questions and concerns below.

1. Is it possible to extend the characterization result in Section 3 to the non-realizable case?

As far as we know it is not possible to extend the result in Section 3 to the non-realizable setting. In general it seems hard to get results for agnostic learning in this model, but we are able to get a nontrivial agnostic learning sample complexity upper bound for the discrete graph model in Section 6.

2. How would the results change if the agent is not assumed to make the "worst case" choice among all points in $\Delta(x)$?

This is a promising direction for future work. Indeed we assume that the agent can make the “worst case” choice in order to make our results robust to the agent’s choice (since they don’t know which points are ground truth positive or negative). We did consider exploring what happens if the agent for example moves to a “random” positive point according to $h$, but this becomes hard to analyze mathematically especially if the improvement set is a continuous region and not discrete points.

3. Are there classes $\mathcal{H}$ which do allow for proper learning under ball improvement sets?

Theorem 3.4 shows that any nearly minimally consistent concept class is properly learnable for all improvement sets and in particular Euclidean balls. This is actually a fairly broad set of concept classes, for example it includes (but is not limited to) all intersection-closed classes such as intervals on a line, rectangles in $\mathbb{R}^2$, polytopes in $\mathbb{R}^d$, etc.

4. What are the possible societal implications of the results, or in which way results can be extended to increase societal impact?

One possible societal lesson from the results is that conservative classifiers perform consistently well when agents can improve. In particular, this means that when setting cutoffs, say for college entrance exams, it is often not harmful to increase the cutoff by a bit because qualified students will always be able to work a bit harder to meet it. On the other hand, it can be very harmful to have the cutoff even slightly below the true cutoff (something that is not usually a problem in standard PAC learning). Quantitatively the paper shows that you can even achieve zero classification error in the learning with improvements model.

We thank the reviewer for their comments and address their questions and concerns below.

1. For the setting in ball improvement set discussed in section 4, if X is bounded, how is the improvement set defined for the points at the surface? Is it the interaction between X and Delta(x)?

Yes, it would be the intersection between $\mathcal{X}$ and the ball of radius $r$ centered at $x$. We meant to write $\Delta(x) = \\{ x \in \mathcal{X}, \ldots \\}$, thanks for catching the typo!

2. In Definition 4.1, D is (epsilon, beta, N) coverable if … radius r. why (epsilon, beta, N) coverable does not depend on r? (e.g., (epsilon, beta, N, r) coverable). Also, why do Theorems 4.2 and 4.3 not depend on r? What if r is infty then?

The parameter $\beta$, which is the probability mass of each ball, implicitly depends on $r$. For example in real applications, if for example the data distribution is uniform over a bounded set in $\mathbb{R}^d$, then a ball of radius $r$ has probability mass proportional to its volume, which is proportional to $r^d$. A larger $r$ (which you can think of as larger $\beta$) actually makes the sample complexity better (the bounds in Theorem 4.2 and 4.3 scale with $1/\beta$), and this can intuitively be seen as well since you can cover the space with less balls and you only need to sample a point in each ball. In the extreme case of $r = \infty$, as soon as there is a positive example $x$ in the training set you can achieve zero error by outputting a hypothesis that is 1 on $x$ and 0 everywhere else, and all other points will improve to $x$.

3. Theorem 3.4 shows a necessary and sufficient condition for PAC-learnable with improvements. However, it seems to be transforming from one definition to another. While it is nice, I wonder if the authors could discuss what it implies? How does nearly minimally consistent help understanding PAC-learnable with improvements?

The implication is that you can check whether a concept class is learnable with improvements by checking a concrete property of the concept class (nearly minimally consistent) unlike the definition of PAC-learnability which deals with all improvement functions and all data distributions. This is the same type of result as the Fundamental Theorem of Statistical Learning, which says that a concept class is PAC-learnable (defined over all data distributions) if and only if it has finite VC-dimension. We show in the proof of Theorem 3.4 that the sample complexity in learning with improvements is also governed by the VC-dimension, but in addition the concept class must be nearly minimally consistent to be learnable.

We thank the reviewer for their comments and address their questions and concerns below.

1. Can you formalize the interaction between the learner and agents using a Stackelberg framework, and explicitly define agent best responses?

As stated in the introduction and Section 2, the formal model is the following: first the learner publishes a classifier $h$, and the agents best respond to this classifier by moving to an arbitrary point $x’$ in the improvement set $\Delta(x)$ such that $h(x’) = 1$ since they want to be positively classified. The classification error is computed based on whether or not $x’$, the point that $x$ moved to, is actually positive according to the ground truth $f^*$. We assume adversarial tie breaking, that is if an agent can move to a point which gets them a positive classification $h(x’) = 1$ but without being truly qualified $f(x’)=0$, then it will prefer to do that. Note that this basic formulation itself is not novel: it was introduced by Attias et al. (ICML 2025), and they also establish the game-theoretic connection.

It is straightforward to view this in the Stackelberg framework. Simply set the utility of the agent to be $1$ at positive points $h(x)=1$, $0$ at negative points $h(x)=0$ and the utility of movement to a point $x'$ within $\Delta(x)$ is something in $[0,1]$. As an example, we could set the utility of movement to $\mathbb{I}[x’ \in \Delta(x)] \cdot h(x’) \cdot$2 - f^* (x’)$/ 3$. This utility is such that the agent has no incentive to move if either $\mathbb{I}[x’ \notin \Delta(x)]$ or $h(x’)=0$, else it has a utility of $\frac23$ for actually negative points $f^* (x’)=0$ and $\frac13$ for actually positive points (so it moves in either case but prefers the former). Note that $\Delta(x)$ is the set of points to which the agent $x$ would ever consider (or is able to) move to, and its incentives to move to a point $x’$ within $\Delta(x)$ are governed by $h(x’)$ and $f^* (x’)$ as described above.

Conversely, our improvement set based abstraction can be used to model an arbitrary utility function as follows. The utility of being positive is $1$ and negative is $0$ (without loss of generality). Movements are associated with cost functions (negative utilities) for each $x\to x'$ move, and costs outside of $(0,1)$ can be ignored (agent either always moves or never moves, irrespective of the classifier). We can define the set $\Delta(x)$ to be the set of points where the cost is in $(0,1)$. Now the agent with $h(x)=0$ would want to move to a point with $h(x’)=1$ as long as it is within $\Delta(x)$, as the net utility is $1 - \text{cost}(x,x’)$, which is positive. We can further incorporate worst-case tie-breaking by defining $\Delta(x)$ to only consist of points with $f^* (x)=0$. We are happy to add this equivalence as a remark (this is alluded to but not explicitly stated).

2. Please clarify how your model compares to strategic classification—can agents both game and improve, or are improvements enforced by assumption?

As stated in the introduction, the agent can move to any point in the improvement set. We call this “improving” rather than “gaming” (the latter term is used in strategic classification) because the agent is genuinely changing their features. What do you mean by “improvements enforced by assumption”? It is not enforced that agents move, but naturally they want to be positively classified so they will of course move to a positive point. Finally, we respectfully disagree with the comment that there is limited comparison to the strategic learning literature and note that we have indeed compared all the results in our model to strategic classification. Every section of our results has a subsection/paragraph comparing the results to strategic classification and we have contextualized the differences in our results on learning with improvements with respect to learnability and algorithm design in strategic classification. See lines [178-186], [249-257], [303-310], [337-340] for example.

3. Can you add examples that illustrate how your algorithms behave on simple input spaces (e.g., linearly separable data under improvements).

Yes, we will add these examples to the paper! It must also be specified what the improvement set is. As an example, in the linearly separable case with Euclidean ball improvement sets, our results in Section 3 and 4 demonstrate that a good classifier should be the smallest halfspace that contains all the positive training examples. If the improvement radius is at least the margin between negatively and positively labeled examples, then one can even get zero error by using this classifier.

4. Can you provide experimental results on synthetic or real datasets to validate your theoretical claims?

This is a theoretical machine learning paper. The results in the paper establish upper and lower bounds on sample complexity and mistake bounds of learning with improvements, which we believe are not suitable to verify experimentally but rather through proofs. Our techniques may inspire future empirical research, for example more conservatively designed classifiers with respect to false positives, to achieve better empirical effectiveness in the presence of improving agents.