PAC Learning with Improvements
Authors: Idan Attias
Avrim Blum
Keziah Naggita
Donya Saless
Dravyansh Sharma
Matthew Walter
Venue: ICML 2025 poster (2025)
Keywords: agents improvement
PAC learning
sample complexity
learning from graphs
Primary area: theory->learning_theory
TL;DR: We show that the learnability of agents that can improve is not characterized by the VC dimension, analyze the sample complexity of learning several fundamental concept classes in this setting and provide an empirical study on real datasets.

Abstract: One of the most basic lower bounds in machine learning is that in nearly any nontrivial setting, it takes at least $1/\epsilon$ samples to learn to error $\epsilon$ (and more, if the classifier being learned is complex).  However, suppose that data points are agents who have the ability to improve by a small amount if doing so will allow them to receive a (desired) positive classification.  In that case, we may actually be able to achieve zero error by just being "close enough".  For example, imagine a hiring test used to measure an agent's skill at some job such that for some threshold $\theta$, agents who score above $\theta$ will be successful and those who score below $\theta$ will not (i.e., learning a threshold on the line). Suppose also that by putting in effort, agents can improve their skill level by some small amount $r$.  In that case, if we learn an approximation $\hat{\theta}$ of $\theta$ such that $\theta \leq \hat{\theta} \leq \theta + r$ and use it for hiring, we can actually achieve error zero, in the sense that (a) any agent classified as positive is truly qualified, and (b) any agent who truly is qualified can be classified as positive by putting in effort.  Thus, the ability for agents to improve has the potential to allow for a goal one could not hope to achieve in standard models, namely zero error.\
In this paper, we explore this phenomenon more broadly, giving general results and examining under what conditions the ability of agents to improve can allow for a reduction in the sample complexity of learning, or alternatively, can make learning harder.  We also examine both theoretically and empirically what kinds of improvement-aware algorithms can take into account agents who have the ability to improve to a limited extent when it is in their interest to do so.

PAC Learning with Improvements
Idan Attias 12
Avrim Blum
Keziah Naggita
Donya Saless?
Dravyansh Sharma Matthew Walter? 2
Abstract
1. Introduction
One of the most basic lower bounds in machine learning is that in nearly any nontrivial setting, it takes least 1/c samples to learn to error (and more, if the classifier being learned is complex). However, suppose that data points are agents who have the ability to improve by small amount if doing so will allow them to receive (desired) positive classification. In that case, we may ac- tually be able to achieve zero error by just being "close enough". For example, imagine a hiring test used to measure an agent's skill some job such that for some threshold 0, agents who score above 0 will be successful and those who score below 0 will not (i.e., learning threshold on the line). Suppose also that by putting in effort, agents can improve their skill level by some small amount r. In that case, if we learn an approximation 0 of 0 such that 8 < 0 < 9 + and use for hiring, we can actually achieve error zero, in the sense that (a) any agent classified as positive is truly quali- fied, and (b) any agent who truly is qualified can be classified as positive by putting in effort. Thus, the ability for agents to improve has the potential to allow for goal one could not hope to achieve in standard models, namely zero error. In this paper, we explore this phenomenon more broadly, giving general results and examining under what conditions the ability of agents to improve can allow for a reduction in the sample complexity of learning, or alternatively, can make learning harder. We also examine both theoretically and empirically what kinds of improvement- awaree al- gorithms can take into account agents who have the ability to improve to limited extent when it is in their interest to do so.
There has been growing interest in recent years machine learning settings where deployed classifier will influence the behavior of the entities it is aiming to classify. For exam- ple, a classifier that maps loan applicants to credit scores and then uses a particular cutoff 0 to determine whether appli- cant should receive loan will induce those below the cutoff value to take actions to improve their score. This setting is called strategic classification (Hardt et al., 2016) or measure management (Bloomfield, 2016) when the actions taken do not truly improve the agent's quality, and performative pre- diction (Perdomo et al., 2020) more generally. In this work, our focus is on the case that the improvements are real e.g., paying off high-interest credit card debt, taking a money management class, etc. for genuinely improving one's loan application. That is, the agent responds to the classifier in order to potentially improve their elassification (Kleinberg & Raghavan, 2020; Miller al., 2020), changing its true fea- tures in the process. The classifier must take this "strategic improvement" response into account.
Unlike previous works on strategic improvement that fo- cus extensively on efficiently incentivizing and maximizing agent improvement (c.g., Miller et al. 2020; Kleinberg & Raghavan 2020; Haghtalab al. 2020; Shavit al. 2020, among others), we aim to understand how agent's capac- ity for improvement impacts learnability, sample complex- ity, and algorithm design for accurate classification. One high-level take-away from our theoretical analysis and em- pirical results is that the ability of agents to improve favors algorithms that are more "conservative" in their decisions. This both due to the reduced concern over false-negative errors (since agents in those regions may still be able im- prove to be classified as positive) and the increased concern over false-positive errors (which may cause individuals to "improve" incorrectly).
To illustrate the potential reduction in sample complexity that result from agents' ability to improve, one of the most basic lower bounds in machine learning is that nearly any nontrivial setting, it takes at least 1/e samples to learn to error (and more, if the classifier being learned is complex). However, if agents have the ability to improve by small amount, we may actually be able to achieve zero error by just being "close enough". To the best of our knowledge, this has
Authors are listed alphabetically. 'University of Illinois at Chicago Toyota Technological Institute Chicago 2 Northwesterm University. Correspondence to: Keziah Naggita <knag- gita stta@ttic.o edu.. Donya Saless <donya@ttic.cdu.>
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

PAC Learning with Improvements
not been previously observed in the strategic improvement literature. Returning to the loan example above, suppose that by putting in effort, agents can improve their credit
ensure that risk-averse student achieves zero-error, and show that providing the labels for the dominating set of the positive subgraph (induced by the true positive nodes) is sufficient.
score by some small amount r, and suppose we are in the realizable case that there is some true threshold 0 such that agents with credit score above 0 will be good customers and those who score below 0 will not. In that case, if we learn an approximation & of f such that 0 < 0 < 0 r and use it as cutoff to determine who should receive loan, we can actually achieve zero error in that (a) any agent classified as positive is truly qualified, and (b) any agent who truly is qualified can get classified as positive by putting in effort. Thus, the ability for agents to improve can potentially allow for a goal one could not hope to achieve otherwise.
In Section 6, we conduct experiments on three real- world and one fully synthetic binary classification tab- ular datasets to investigate how the error rate of a model function (h) decreases when test-set agents that it initially classified as negative improve. Our results indicate that while risk-averse models may start with higher error rates, their errors rapidly drop the negatively classified test agents improve and the improvement budget (r) increases. A stricter penalty for false positives typically leads to more accurate positive classifications, resulting in greater gains from agent improvements. In most cases, test er- rors decline sharply, sometimes reaching zero (e.g.. in Figure 10g).
We also observe fundamental differences in the inherent learnability of concept classes, compared to both standard PAC learning where the agents cannot respond to the classi- fier, as well as the strategic PAC setting where the agent tries to deceive the classifier to obtain a more favorable classifi- cation. Somewhat surprisingly, learning with improvements can sometimes be easier than the standard PAC setting, and it can sometimes be harder than strategic classification. We show that proper learnability with improvements in the re- alizable setting is closely linked to the concept class being intersection-clast closedd.
Related Work. Learning in the presence of strategic ("gaming"), utality-maimiiiigg agents has gained increas- ing attention in recent years (Hu et al. 2019; Milli et al. 2019; Braverman & Garg 2020; Ahmadi et al. 2021; Hagh- talab et al. 2020, among others). Early research framed this problem as a Stackelberg competition (Hardt et al., 2016; Brückner & Scheffer, 2011), where negatively classified agents manipulate their features to obtain more favorable outcomes if the benefits outweigh the costs. Kleinberg & Raghavan (2020) extend this model by considering agents who can both manipulate and genuinely improve their fea- tures, proposing a mechanism that incentivizes authentic improvement. This model has been studied under a causal lens, where the learner may not priori know which features correspond to manipulation or improvement. Strategic learn- ing from observable data requires solving a causal inference problem in this setting (Miller et al., 2020), and the ability to test different decision rules can be helpful (Shavit et al., 2020). Ahmadi et al. (2022) consider a similar setting and propose classification models that balance maximizing true positives with minimizing false positives.
Concretely, our contributions are as follows:
In Section 3, we show separation between the standard PAC model and our model of PAC learning with improve- ments. Specifically, we show that a finite VC dimension is neither necessary nor sufficient for PAC learnability with improvements. We further show a similar separation from the more recently studied PAC model for strategic classification (Hardt et al., 2016; Sundaram et al., 2023). In Section 4, we study learnability of geometric concepts in Rdd We show that any intersection-closed concept class is learnable under our model, and show that the generalization error can be smaller than the standard PAC setting for interesting cases including thresholds and high-dimensional rectangles. We also show that the intersection-closed property is essentially necessary for proper learnabiliyy in setting.
We extend this line of work by analyzing the inherent learn- ability of classes, the sample complexity of learning, and the ability to achieve zero-error classification, when agents can truly improve. Inherent learnability of concepts has been studied in the strategic manipulation setting (Sundaram et al., 2023; Cohen et al., 2024; Lechner & Urner, 2022), but not in the strategic improvement setting. In Section B.2, we show how our improvement setting differs from strategic manipu- lation with respect to learnability. The sample complexity of learning in the presence of purely improving agents has been studied by Haghtalab et al. (2020), but from a social welfare perspective where the goal to maximize the true positives after improvement. In contrast, our primary focus is classi-
In Section 5, we study a graph model in which each node represents an agent and the improvement set of an agent is the set of its neighbors in the graph. We establish near- tight bounds on the number of labeled points the learner needs to see to learn a classifier which achieves zero error with high probability, given the ability to learn the labels of uniformly random nodes. We further show that it is possible learn "fairer" classifier that also enables improvement whenever it leads to a better classification for an agent. We also study teaching setting where the teacher aims to find the smallest set of labels needed to
OOr code publicly available here.
2

---

PAC Learning with Improvements
fication error, which is more sensitive to false positives. In Section 5.2, show that these two objectives need not be in conflict and may be simultaneously optimized. Finally, the ability of learner to achieve zero-error for non-trivial concept classes and distributions has not been previously observed in any strategic or non-strategic setting.
Otherwise, the agent reacts and moves to be predicted pos- itive by h. This corresponds to maxiiiy-maximiiing agents that have a utility of 1 for being classified as positive, a utility of 0 for being classified as negative, and that incur a cost for moving, where A (xr corresponds to the points that æ can move to at a cost less than
Our work also relates to research in reliable machine learn- ing (Rivest& & Sloan, 1988; El-va & Wiener, 2010), where learner may abstain from classification avoid mistakes, balancing coverage (the proportion of classified points) against error. In contrast, we strive for a zero false positive rate and minimal false negative rate, aligning with learning under one-sided error (Natarajan, 1987; Kalai et al., 2012). We include more detailed discussion of the related work in Appendix A.
We say that a test point x has been misclassified if there exists point in the reaction set of where h disagrees with f", formally,
ho.
max x'EAn(2)
+f (I)
Remark 2.1. The formulation of the loss function in (I) allows for scenarios where input x initially satisfies [xx) = 1 and h((r) = 0, but under (x)), it may transi- tion to a setting where f (x²) 0 and h(x²) 1 for some x' E Ax(z). Think of an example where there are two features such that improving one often comes at the expense of the other. For instance, consider the trade-off between strength and endurance in athletics. Let fax) represent a person's endurance (e.g., marathon running capability), and h(z) represent their strength (c.g., sprinting power). Focus- ing on increasing h(x) through strength training enhances power, but this often comes at the expense of endurance, thus reducing (xx). This reflects the natural conflict be- tween optimizing for one feature while sacrificing the other.
2. Formal Setting: PAC Learning with Improvements
Let X' denote the instance space consisting of agents with the ability to improve, defined below. We restrict our attention to the case of binary classification, i.e., the label space is {0, 1}. Without loss of generality, we refer to label O as the negative class and label 1 as the positive class. Let A X + 2x denote the improvement function that maps each point (agent) x E X' to a set of points (xx) (the improvement set) to which can potentially improve itself in order to be classified positively. For example, if X' is metric space, can define (zz) as the by-ball centered at xr Let H. S. (0. 1)x2 denote the concept space. We will focus on the realizable setting, i.e. we assume the existence of an unknown (to the learner) target concept f : X - {0, 1} that correctly labels all points in X' and satisfies f E H.
In words, this corresponds to an assumption that agents will improve to point in their reaction set while breaking ties ad- versarially, or equivalently, that they will break ties in favor of points x' for which f (z') = O. This assumption is natu- ral if we want our positive results to be robust to unknown tie- br-akeeking mechanisms, and would also hold if improving to points x' E An(s) whose true label according to f" is negative is less effort than improving such points whose true label is positive. Note that this loss function favors classi- fiers that label uncertain points as negative rather than pos- itive. For example, if {a f(x) = 1] S fx f (x) = 1} then h may still have zero loss if all points x in the differ- ence have at least one point x' E (xx) for which f((²') 1. The fact that true positives might need to put in effort to improve in order to be classified as positive (or that some negative points are not able to improve themselves to be classified as positive by h even if they would have been able to do so with respect to f*) does not count as an error in our setting.
The intuition behind the model is as follows. The learner first publishes classifier h X {0, 1} (potentially based on some data sample labeled according to f*), We will refer to this function h as the learner's hypothesis. Each agent then reacts to h (Zrnic et al., 2021; Hardt et al., 2016)-if it was classified negatively by h, the agent attempts to find a point in its improvement set that is positively classified by h and moves it. Note that the agents do not know the true function f and as a result cannot react with respect to the ground truth, only based on h.
We formalize this as the reaction set with respect to h,
(x(x) - {ar if f(x)) 1, 1z f2' E A(x) | M(x') = 1] U. A())) Mx²'= 13 otherwise.
See Section 4.1 for a concrete example.
Analogous standard PAC learning, assume the learner has access to a finite set of samples S E x drawn ran- domly according to some fixed but unknown distribution D over X, and labeled by f" The learner's population loss is given by Lossp (, f*) = PAND [Loss(x; h, f*)]. This is formalized in the following.
In other words, if h classifies as positive, the agent x stays in place and does not attempt to improve. If h classifies x as negative, there are two types of reactions. Either, there is no point in its improvement set that can improve the agent's 's classification according to h and the agent again stays put.
3

---

PAC Learning with Improvements
Definition 2.2 (PAC Learning with improvements). Algo- rithm A PAC-learns with improvements a concept class H with respect to improvement function A and data distribu- tion D using sample size M == M(e, 6, A, H. D)². if for any l E H. any > 0 and >> 0, the following holds. Algorithm A, with access to a sample S Ltd ~ DM labeled according to f* produces with probability least 1-6 a hy- pothesis h: X' + {0, 1} with Loss (h, f*) S We fur- ther say that A learns H w.r.t. A and D with zero-error with sample size M if for any 8 > O, given S 1id DM labeled by fr, it returns h with Lossp(h, f*) = O with probability at least 1 - 5. We will also consider distribution- -irreeitioo-dddeeedeent learning, where the guarantee should hold for all distribu- tions D and proper learning where we require h E H.
if PPPEDDDS 1] S c, then h will have error at most e with probability 1.
Example 2 (Finite VC dimension is not sufficient for learn- ability with improvements). Let the instance space X' be [0. 11, let H. = {hated (abbed(z) = iff x E [a, b) (c, d} (i.e., H is the class of unions of two intervals, where to make the example casier, we define the intervals to be half-open), and let D be the uniform distribution over [O, 1]. We define A as follows. For I E [0. 1/4) U (3/4, 1] let ((x) = [0. 1]; for x E (1/4, 3/4], 4). let A(x) = (x)-
We claim that no algorithm with finite training data can guarantee an expected error of less than 1/4, even though the class is easily PAC-learnable without improvements.
Consider a target function defined as the union of two inter- vals [1/4, b) U (b. 3/4] where the number b was randomly chosen in [1/4, 3/4]. With probability 1, the learner will not see the point b in its training data, so it learns nothing from its training data about the location of b. Finally, if the learner outputs a classifier whose positive region has proba- bility mass I 1/4, then its error rate is at least 1/4 because the positive examples cannot move so at least half of their probability mass will get misclassified. On the other hand, if the learner outputs a classifier whose positive region has probability mass greater than 1/4, then it has at least a 50% chance of including a negative point in its positive region (it will surely include negative point if it is not contained in [1/4, 3/44 and has least a 50% chance of doing so other- wise, since b was uniformly chosen from [1/4, 3/4). If the classifier has a negative point in its positive region, then it will have an error rate at least 50% because all the negatives in [0, 1/4) and (3/4, 4, 1] will move to a false positive (here we use that agents break ties adversarially). So, either way, its expected error is 25%.
Note that in our learning with improvements setting zero- error can be achieved by learning (with high probability) from finite sample in several interesting cases, which is impossible to achieve in the standard PAC model.
3. Separating PAC Learning with Improvements and the Standard PAC Model
In this section, we prove that learning with improvements diverges from the traditional behavior of the standard PAC model for binary classification. In the PAC model, the learn- ability of a concept class is equivalent to the class having a finite VC dimension. However, in our setting, where agents can improve, this condition is neither necessary nor suffi- demonstrate that
cient for learnability. Concretely, class with an infinite VC dimension can still be learnable with improvements. We also provide examples of concept classes with finite VC dimensions and corresponding im- provement sets that cannot be learned in our framework.
Theorem 3.1. Finite VC dimension is neither necessary nor sufficient for PAC learnability with improvements.
Union of two intervals is arguably the simplest class that is not intersection-closed (Definition 4.3). Indeed, we show in Section 4.2 that such an example could not be possible for intersectooncloser classes. As another example of the separation of our model from the standard PAC setting, we show it is possible that for some target function I* the learner using a hypothesis space H. achieves no eиror in the standard PAC setting, but it is impossible to avoid constant error rate when learning the same target with improvements using the same hypothesis space H.
Proof. The proof is in Examples 1 and 2 below.
Example 1 (Finite VC dimension is not necessary for learn- ability with improvements). Consider any class H of in- finite VC-dimension, and define A(x) = X' for all ex- amples x E X. We can learn this class H with respect to this improvement function A with sample complexity M (e, 6) = In(3 ( for any data distribution D as follows. First, draw sample S of size M(c, 8). Next, if all examples in S are negative, then output the "all-negative" classifier; otherwise, select any positive example I² e S and output the classifier h(x) = I[x = 2=). Note that in the latter case, the hypothesis h has error zero, because all agents will improve to x² Therefore, if (x) = 1] > e, then h will have zero error with probability at least 1 5, whereas
Theorem 3.2. Consider a hypothesis class H and target function '* E H. Let d(f", H) denote the error of the best hypothesis in H w.t.. the target f It is possible to have ddf"", ,H) = in the standard PAC setting (there exists h E H that achieves error 0) but d(f", H) 1/2 for PAC learning with improvements (i.e., all h H have error at least 1/2).
We say the sample complexity of A is the smallest such M.
Proof. See Example 3 in Appendix B.
4

---

PAC Learning with Improvements
We further show separation of our model from strategic classification in Appendix B.2. Remarkably, learning with improvements may be either easier or harder than strategic classification depending upon the setting.
+
he
higt
Figure 1. Learning thresholds with improvements.
4. PAC Learning of Geometric Concepts
In this section, we first demonstrate the gain of the learner when agents can improve for the natural class of thresholds on the real line, where agents can move by distance of at most We then study intersection-closed classes. In particular, we derive sample complexity bounds for the class of axis-aligned hyperrectangles, where the improvement sets are the foe balls. We further establish negative results for proper learners in the absence of the intersection-closed property. Lastly, we study the class of homogeneous halfssaaces under the uniform distribution over the unit ball, where agents can improve by adjusting their angle. Complete proofs for this section are located in Appendix C.
[0, 1.. For any e, E (0,1/2), with probubility 6,
Lossp(hg hr S (E r)
with sample complexity M 0 ( log z
Proof. See Appendix C.I
Note that the population error improved from e (in the standard PAC setting) to e- for the same sample size, and achieve zero error as long as we set
We will use (a)+ to denote max(a,0) 0}.
Theorem C. in Appendix C.2 proves similar result for arbitrary distribution DD where instead of getting pop- ulation error, the reduction in the error is replaced by the following distribution depedden quantity
4.1. Warm-up: Zero Error for Learning Thresholds
Let H. = {hr : t } be the class of one-sided threshold functions, where ht (z) = If 2 t}. The improvement set of x is simply the closed ball centered at x with radius r, i.e., x'| S r). Suppose the data distribution D is uniform over [0, 1]. and labels are generated according to target threshold fy-
((hst:he- D D,
POND (ar [ts+ rsts+]]- (2)
A A(x) {a'
Note that the class of thresholds is closed under intersection: Ni=n h4, = [tmax(t),fa...-d J. In the following, we extend the analysis to such concept classes, more generally.
H. for some t* E [0, 1]. Let S (11, U1) )m be the set of training samples, where
iid. Tt ~ D and = b2- (z,).
4.2. Intersection Closed Classes
There are several options for choosing a threshold that achieves zero empirical error on S, as shown by the shaded area in Figure 1. Due to the asymmetry of the loss function (Eqn. 1), we choose the rightmost threshold consistent with S. This is the most "conservative" option, any that im- proves up to this threshold is guaranteed to be positive with respect to the unknown ground-truth he. This is a property that would not necessarily hold for lower thresholds. We define this threshold with respect to S as follows,
The learnability of intersection-closse concept classes in the standard PAC model has been extensively studied (Helm- bold et al., 1990; Auer, 1997; Auer & Cesa- Besa-Bianchh, 1998; Auer & Ortner, 2007: Darnstädt, 2015). In this section, study the learnability with improvements of these classes. We start with the following definitions.
Definition 4.2 (Closure operator of set). For any set S C X and any concept class H C 2 the closure of S with respect to H. denoted by CLOSx(S): 2x 2 is defined as the intersection of all functions in 7. that con- tain S, that is, CLOSx = N h. In words, the heH,sCh
min(s+),
if S + 0, if 5 = 0,
1ss
1,
where S+ foy E S 1} is the set of posi- tive examples in S. The hypothesis hgi is defined as hi+ = 1[x 2 ts+ J. Notice that using classifier hs+ will induce agents (at test time) E [ts+ r, ps+s+ to improve to be classified as positive by hg+, which will be a correct classification since tst 2 t".
closure of S is the smallest concept in H which contains S. If (h- E H. S C h} = 0. then CLOSH = X.
Definition 4.3 (Intersection-closeed classes). A concept class H. 2 is intersection-closee if for all finite S C X, CLOSS#()) E H. In words, the intersection of all functions in H. containing an arbitrary subset of the domain belongs to H. For finite concept classes, an equivalent definition states that for any h1 h2 E H. the intersection hy O h2 is in H as well (Natarajan, 1987).
Theorem 4.1 (Thresholds, uniform distribution). Let the improvement set A be the closed ball with radius r, A(x) = {ol Jx x' S r}. Let 'D be the uniform distribution on
5

---

PAC Learning with Improvements
Many natural concept classes are intersection-closed, for example, axis-parallel d-dimensional hyperrectangles, in- tersections of halfspaces, k-CNF boolean functions, and subspaces of a linear space.
Theorem 4.6 (Axis-aligned Hyperrectangles). Let the im- provement set A be the closed Es ball with radius r, A(x) -x' || -''lle S rJ. Let Rtg be the rectan- gle returned by the closure algorithm given S lid D'n, and R be the target rectangle. For any distribution D, for any c, 8 E (0, 1/2), with probability 1 -6,
The Closure algorithm is a learning algorithm that generates a hypothesis by taking the closure of the positive examples in given dataset, and negative examples do not influence the generated hypothesis. The hypothesis returned by this algorithm is always the smallest hypothesis containing all of the positive examples seen so far in the training set.
Losso (fg, R*) S -PaDD (xr IR(RR: R", A))+
with sample complexity M M- O (: (d (og+log] log
When D is the uniform distribution on [0, 1f², we can get the following expression. Denote by 11 and l2 the width and height (respectively) of the rectangle Hg.. Then,
Definition 4.4 (Closure algorithm Natarajan, 1987; Helm- bold et al., 1990). Let f E H and let S = {(11.3) = (((1))..... (Tm, Mm f (xm)) }]} be a set of labeled ex- amples, where each vi E X' The hypothesis h& produced by the closure algorithm is defined as:
P P2-D [x E IR(H;; R R", A]]] 2r(1 12) + 47
kg(() -(1, f1, i CLOSH (f2; ES:: V. 1}), otherwise.
Note that, as opposed to the simple case of thresholds, the improvement region for hyperrectangles depends on the geometry of the target concept.
Here, CL.OSH ((r; E S: y 1)) denotes the closure of the set of positive examples in S with respect to H.
Arbitrary Intersection-closedd Classes We will now show that any intersection-closee concept class with a finite VC dimension is PAC learnable with improvements w.r.f. any improvement function A.
The closure algorithm learns intersection-closed classes with
VC dimension d with an optimal sample complexity of @ (d + log })) (Auer& & Ortner, 2007; Darnstädt, 2015).
Theorem 4.7. Let H be an intersection-closed concept class on instance space X. There is a learner that PAC- learns with improvements H with respect to any improve- ment function A and any data distribution D given a sample of size O (dve (H) + +log f)), where dyc(H) denotes the VC-dimension of H.
We apply the closure algorithm for learning with improve- ments. In order to quantify the improvement gain of the returned hypothesis, we define the improvement region of h as the set of points that can improve from a negative classification to a (correct) positive classification by h.
Proof Sketch. Note that the closure algorithm outputs hy- pothesis he which exactly classifies the positive agreement region as positive. By known results for intersection-closee concept classes, we have that O (2 (dvc(?) + log })) ex- amples are enough to guarantee that the error of h is less than é in the standard PAC learning setting. Note that any point that he classifies as positive is positive according to f*, Now if the negative points move in response to h and get positively classified by ht, they must become truly positive. Thus, for the stated sample size, the error can only decrease with improvements below e. This is quantified by the proba- bility mass under D of the points in the improvement region, as defined in Eqn. 3. Intuitively, if H is an intersection- closed class in Rd and A is the Eo ball of radius r, then the improvement region constitutes strip of width r along the boundary of he (a (d 1) -iddiennsional hypersurface). O
Definition 4.5 (Improvement Region). The improvement region of hypothesis h S f", w.r.t. f* and A is
IR(h; A) = (x: ((x) = 0, Are E A(x): Mx))= = s- 1}.
(3)
The gain from improvements is the probability mass of the improvement region under D: PAND [x E IR(h; f", A)].
Note that for the class of thresholds, the closure algorithm returns exactly the hypothesis hg-, and the probability mass of the improvement region is p(hs+; ; her, D, (cf. Eqn. 2).
Axis-A Aligned Hyperrectangles in [0, 1] An axis-aligned hyperrectangle classifier assigns a value of 1 to a point if and only if the point lies within a specific rectangle. For- mally, let a = (a1..... ad), = (b...... bu) E [o, 1]d where a; S by for E (1...., d}- = [d]. hyperrectangle R(a,b) = Il lag, bi] classifies point x = (2), (#),)..,.2)) x2) as: R(a,) (x) = H[x E [a., by], Vi E [d]]
We can also establish the following negative result which indicates the hardness of proper learning in the absence of the intersection-closed property.
In the following, we show that the closure algorithm learns with improvements the concept class Hree = (Raa)) : a, E [o, 1]9).
Theorem 4.8. Let H be any concept class on a finit in- stance space X' such that at least one point x' E X is clas- sified negative by all h E H (i.e. {a h((x)) = 0 for all
6

---

PAC Learning with Improvements
H} + 0), and suppose H layta' y is not intersection-clovee on X') \, {x'). Then there exists a data distribution DD and an improvement function A such that no proper learner can PAC-learn with improvements H. w.r.t A and D.
zero error may be attained even in this general setting. All proofs in this Section are deferred to Appendix D.
Formally, let G = (V, E)) denote an undirected graph. The vertex set V = { T2............ .n represents a fixed collec- tion of n points corresponding to a finite instance space X. The edge set E C V x V captures the adjacency in- formation relevant for defining the improvement function. More precisely, for given vertex z V. the improve- ment set of x is given by its neighborhood in the graph, i.e. Axx) = {z' E V (x, E E)}. Let I V - {0, -1] represent the target labeling (or partition) of the vertices in the graph G. Assume that the concept space H is the set of all possible labelings of the graph, which is finite.
Note that we have an additional requirement that all clas- sifiers in the concept space agree on some negative point (intuitively, agents who should never achieve positive classi- fication). Consider the following simple example where this condition does not hold, the concept class is not intersection- closed, and learnability is possible in our setting.
Suppose X' {a1, ] and H. {h1, b22 with h (x1) = 1, N1 (22) = 0 and (1x) = 1 (x) for either X. Clearly 11 O f2 & H and H is not intersection-closed, yet knowledge of single label tells us the target concept.
5.1. Near-tight Sample Complexity for Zero-error
4.3. Halfspaces on the Unit Ball
Our first result is to show that we can obtain zero-error in the learning with improvements setting, when the data distribution D is given by a uniform distribution over V, and obtain near-tight bounds on the sample complexity. Our learner in this case is the conservative classifier h E H that classifies exactly the positive points seen in the sample as positive, and the remaining points as negative. Even though we allow f* to be an arbitrary labeling in H. we do not need to see all the labels to learn an h that achieves zero error w.r.t. f Intuitively, this is because for any positively labeled node it is sufficient to see the label of x or that of one of its neighbors since the agents can move to neighbor predicted positive by h. We further show that no algorithm can achieve better sample complexity, up to some logarithmic factors.
We now consider the problem of learning homogeneous halfspaces with respect to the uniform distribution on the unit ball (or any ppherically-symmeed agents have the ability to improve by an angle of
distribution), when
Theorem 4.9. Consider the class of d-dimensional hulf- spaces passing through the origin, ie., H fx + sign(w"x)) w E Rdd. Suppose X is the surface of the origin-centered unit sphere in Rd for d > 2, and 'D is the uniform distribution on X. For each point X, define its neighborhood ((x) {{a arccos((x, (xx,"")) x')) S r}. For any E (0,1/2), and train- ing sample S ~ Dm of size Ô ( (dtlog 1 with probability (POSH
1 1, 5, intersection of the positive regions of all h E H consistent with the training set S.
O, where POSx(S) is the
Theorem 5.1. Let G (V, E) be an undirected graph with IV| vertices, and let f : V + {0, +1} de- note the ground truth labeling function. Let d denote the minimum degree of the vertices in G+, the induced subgraph of G on the vertices x E V with f*(x) = 1. As- sume that the data distribution D is uniform on V. For any 5 >> O. and training sample 5 itd. Dm of size m O m[llog n+log +) there exists learner that achieves zero d +1
Remark 40 It is worth noting that while the aforemen-
tioned result relies on the classifier POS(Hs), which is a fairly complex function, a similar guarantee can be achieved using a linear classifier (though non- non-homogeneous, so it is still not "proper"). Specifically, by obtaining a sufficiently large sample, one can construct homogeneous linear clas- sifier whose angle with respect to the target is most 5. We can then shift that classifier by r/2 (so it is no longer homo- geneous) to ensure its positive region is contained inside the positive region for f".
generalization error, i.e. learns a hypothesis h such that LOssp f*)= ==)=00 0, with probability at least 1 - over the draw of S. Moreover, there exists a graph for which any learner that achieves zero generalization error must see at least Ω +i log - labeled points in the training sample, with high constant probability.
5. Zero-error Learning in the Graph Model
We note that the value of d+ (and, therefore our bound on the sample complexity) is generally not known to the learner in advance, and depends on the graph structure as well as the (unknown) target labeling f It an interesting open
In this section, we will consider a general discrete model for studying classification of agents with the ability to improve. The agents are located on the nodes of an undirected graph, and the edges determine the improvement function, i.c. the agents can move to neighboring nodes in order to potentially improve their classification. Note that the graph nodes corre- spond to an arbitrary discrete instance space X., Remarkably,
*Our results readily extend to A(x) = {a' E V do(a, x') S r). where de denotes the shortest path metric on G. by applying our arguments to G", the n power G (see appendix).
7

---

PAC Learning with Improvements
question to design a learner that can determine whether sample of sufficient size has been collected to guarantee zero-error. For the special case of the complete graph, our sample complexity bound becomes m = Ō n where a+ is the number of nodes labeled positive by f
D.2) for the risk-averse student learn a zero-error classifier h. This observation also motivates and helps establish our learning result (Theorem 5.1).
Theorem 5.2. Let G EV,E) be an undirected graph, and f be the target labeling. Let G denote the induced subgraph on the vertices x E V with (x) 1, and S de- note the dominating set G Then Loss (r; h for any x E V, where hi++ (x) = 1 E St).
5.2. Enabling Improvement Whenever It Helps
Note that our loss function Loss h, f* penalizes the learner for mistakes w.r.t. the target /* after the agents have potentially reacted to h. However, we say nothing about whether a negative point æ that truly has the ability to im- for some o' E Axx)) will also be able to do under our published classifier h. We will now consider an alternative measure of the performance of h (conceptually captures recall in the improvement setting) which measures the probability mass of the points for which we fail to enable improvement even though it is possible under f". Formally, we define
Proof. See Appendix D.4.
prove and get positively classified (i.e. (x²)
6. Evaluation
Below and in Appendix E, we present the setup and re- sults of our evaluation of improvement-awwar algorithms, focusing on practical risk-aversion strategies, specifically loss-based and threshold- methods. These strategies align with our theory, which predicts optimal performance for risk averreverse classifiers when agents improve under lim- ited budget r. We also investigate whether, and under what conditions. model error can be driven to zero when agents can improve within an loo ball of radius r. Achieving zero error is a notable property in the learning with improve- ments setting, even for broad concept classes (ef. Section 5, where the instance space is discrete and concepts may be arbitrary functions). Our code is available here.
(h,, = PAND [ (x) = A
(4)
-= = {x}]]
That is, we wish to ensure that an agent x with (x) 0 and an option to improve to a truly positive point in its re- action set w.r.t. fe, will also see some option to improve and get positively classified according to h. In Theorem D.4 in the Appendix, we obtain near-tight sample complex- ity bounds for learning a hypothesis h that simultancously guarantees that Loss (h, )**) 0 and Lossp(h, f*) 0 when the data distribution is uniform over V.
Datasets. We use three real-world tabular datasets: the Adult UCI dataset (Becker & Kohavi, 1996), the OULAD and Law School datasets (Le Quy et al., 2022a), and a synthetic 8-dimensional binary classification dataset with class separability 4 and minimal outliers, generated us- ing Scikit-learn's 's make_cle cac.asssiii.... fication function (Pe- dregosa et al., 2011). In each case we train zero-error model f* on the entire dataset, which we treat as the true labeling function for our experiments.
5.3. Teaching a Risk-averse Student
The theory of teaching (Goldman & Kearns, 1995) studies the size of the smallest set of labeled examples needed to guarantee that a unique function in the concept space is con- sistent with the set (for labels according to any target concept in the space). If the teacher (that knows f*) provides this labeled set, then student that can do consistent learning (find a concept consistent with training data) will learn the target concept f". In our learning with improvements over the graph setting, it is natural to consider a simple variant where the student outputs the most risk-averse concept that only labels positive points seen in the labeled set received from the teacher as positive. Here we will consider the question of the minimum number of labeled examples the teacher needs to provide to the risk-averse student to achieve zero-error in our setting.
Let ST = {(x, y) I E Rdd E (0, represent the dataset (e.g., Adult), where x is the feature vector and y = (xx is the label. For all experiments, we split Sr into training Swain (70%) and testing Sist (30%) subsets. Further dataset details, including improvement features and class distributions, are provided in Appendix E.
Classifiers. For each full dataset Sy. we trained zero-error model f using decision trees. We trained the decision- maker model h .dd + {0, 1). taking the form of a two- layer neural network, on Smain with tuned hyperparameters. To assess the loss function's 's impact on error drop rate when agents improve, trained both standard model with binary cross-entropy (Lucr) loss and risk-averse model with weighted- (CwBCE) loss.
Let G+ denote the induced subgraph of G on V+ = {o E V fz) = +1}, the nodes labeled positive by the target concept f We show that it is sufficient for the teacher to present the labels of dominating set of G+ (Definition
1 LARCE
Σ
W si) log(1 - (c) + wENy log( (5)
12 k=1
8

---

PAC Learning with Improvements
CaCE
... Cusce [Wyp= 3,0)
Cuece (Wp 6.0)
Cacr
Caace, (Wyp
Caece, (Wir
(Wyp 1.0)
Cwster (Wi 7.0)
Evcce, [W* = 1.0)
(W = 4.00
7.0)
Easce, (wer = 2.0)
- fuece, (Wyp = 5.0)
Evecz. (wer = 8.0)
Eudct- (Wyp - 2.0)
Cuzce. (Way - 5.0)
Caace. (Wyp 8.D)
0.8
Model (h) Error
0.20
0.7
0.6
0.15
0.5
0.10
Model
0.05
0.1
0.00
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
improvement Budget (r)
Improvement Budget
(a) Adult (LWBCE where upy = 0.001)
(b) Law school (CoNce where wan 0.01)
Figure 2. We compare the performance gains when agents improve to the risk-averse (CWRCR, wie 1, WTP (1) and the standard
wey (Cace, WPP = WFx = 1) models across the Adult and Law School datasets using a fixed classification threshold 0.5. Higher improvement budgets (r) and greater risk-aversion (high wa) accelerate error reduction. See Figure 10 (Appendix) for full results. wpy
where, = |Smail E {0, 1 is the true label, 1 E (0, 1] is the model prediction, and Wyp and WpN are the false positive and false negative weights, respectively. Setting wpp = WPN- = 1 in LEEE recovers LECE-
after agent movement and exhibit marked decline in false negatives as the improvement budget increases (Appendix, Figure 9). Among risk-averse strategies, loss-based risk aversion, where L -triined models use are > outper- forms threshold-based approaches that classify agents as positive only if predicted probability exceeds 0.9 (Figure 2). Second, modest improvement budgets (r S 2.0) lead to sub- stantial error reduction, but returns diminish for (r 2.0), especially with decision threshold of 0.5. Third, dataset class separability (Appendix, Figures 6 and 7) significantly affects the optimal level of risk aversion and the relationship between improvement budget and error reduction.
Beyond the LWCCE loss function, which penalizes false posi- tives more heavily, we explore another form of risk-averse classification by applying higher threshold of 0.9 (instead of the usual 0.5) to the sigmoid output of the final layer. For further details, refer to Appendix E.2.
Improvement. Given a trained model function h, a data sample x Sust with an undesirable model outcome h(x) = 0. and a subset of improvable features along with predefined improvement budget r, we use Projected Gra- dient Descent (Madry al., 2018) to compute the minimal change within the budget required to transform x into positive outcome h(=')= 1. Specifically, we aim to find:
In summary, risk-averse models initially incur higher errors but achieve rapid error reduction agents improve and increases. A stricter false-positive penalty improves the positive agreement region, reducing test error, sometimes to zero (e.g., Appendix, Figure 10g).
x' = (roja(()) (o)))) + or signnning aaco h(z))) (6)
7. Discussion
such that h(x)) 1. Here, (L(h(z))) h(x)) represents the gradient of the loss function (BCE wBCE), t the current iteration, and the step size. Proja(z) denotes the projection of (x) onto the Eox ball of radius r' centered at x, A(x) (=(o) E Rdd; | x/|,00 Sr. This ensures that updates remain within the r-blll constraint. A successful improvement occurs when a negatively classified sample x transforms within the specified budget r into x' such that M(x')= = and (x') (see Appendix E.3).
We propose a novel model for learning with strategic agents where the agents are allowed improve. Surprisingly, are able to achieve zero error (with high probability) by designing appropriate risk- learners for several well- studied concept classes, including a fairly general discrete graph-based model. We show that the VC dimension the concept class is not the correct combinatorial dimension to capture learnability in the context of improvements. We fur- ther show that the intersection-closie property is sufficient, and in a certain sense necessary for proper learning with respect to arbitrary improvement sets. We leave open the questions of fully characterizing proper PAC learning with improvements and characterizing improper PAC learnability with improvements in terms of the concept class and the improvement sets available to the agents.
Results. We highlight three key findings from our evalu- ations (see also Appendix E.4). First, risk-averse (wBCE- trained) models consistently outperform standard (BCE- trained) models in reducing overall error as the improve- ment budget increases (Figures 2, 8, and 10). While er- ror gains relative to BCE-tran trainedid models tend to cancel out, wBCE-trrined models retain low false positive rates

---

PAC Learning with Improvements
Acknowledgments
Attias, I., Hanneke, S., and Mansour, Y. A characterization of semi-supervised adversarially robust PAC learnability. Advances in Neural Information Processing Systems, 35: 23646-22 -2659,, 2022a.
This work was supported in part by the National Science Foundation under grants CCF-2212968, ECCS-221680 2219999, and ECCS-2217023, by the Simons Foundation under the Simons Collaboration on the Theory of Algorithmic Fair- ness, and by the Office of Naval Research MURI Grant N000142412742.
Attias, I., Kontorovich, A., and Mansour, Y. Improved generalization bounds for adversarially robust learning. Journal of Machine Learning Research, 23(175):1-31 2022b.
Impact Statement
Auer, P. Learning nested differences in the presence of malicious noise. Theoretical Computer Science, 185(1): 159-175, 1997.
Our work centers on individuals' capability strategically improve in response to decision-making algorithms, and the effect this has on the kinds of guarantees that one can hope to prove for machine learning algorithms. Our findings can potentially help inform decision-makers to design better algorithms. However, our main contributions are primarily theoretical in nature, and we anticipate no direct social im- pact of our work. We nonetheless believe there is a valuable opportunity to leverage our findings in ways that support both decision-makers and the individuals subject to these algorithms. To realize this potential, future research must critically assess the ethical and practical consequences of deploying improvement-avee algorithms, particularly in high-stakes domains.
Auer, P. and Cesa-Bianchi, N. Online learning with mali- cious noise and the closure algorithm. Annals of mathe- matics and artificial intelligence, 23:83-99, 1998.
Auer, P. and Ortner, R. A new PAC bound for intersection- closed concept classes. Machine Learning, 66(2):151- 163, 2007.
Awasthi, P., Balcan, M.-F., and Long, P. M. The power of localization for efficiently learning linear separators with noise. Proceedings of the forty-sixth annual ACM Symposium on Theory of Computing (STOC), 2013.
Balcan, M.-F. and Haghtalab, N. Noise in Classification. In Beyond the Worst- Worst-Case Analysis of Algorithmss 2020.
References
Ahmadi, S., Beyhaghi, H., Blum, A., and Naggita, K. The Strategic Perceptron. In Proceedings of the ACM Confer- ence on Economics and Computation (EC). pp. 6 22, 2021.
Balcan, M.-F,, Blum, A., Hanneke, S., and Sharma, D. Robustly-reliable learners under poisoning attacks. In Conference on Learning Theory, pp. 1499-45344 PMLR, 2022.
Ahmadi, S., Beyhaghi, H., Blum, A., and Naggita, K. On Classification of Strategic Agents Who Can Both Game and Improve. In Proceedings of the Symposium on Foun- dations of Responsible Computing (FORC), 2022.
Balcan, M.-F., Blum, A., Sharma, D., and Zhang, H. An analysis of robustness of non-Lipschitz networks. Journal of Machine Learning Research, 24(1), January 2023a. ISSN 1532-4435.
Balcan, M.-F., Hanneke, S., Pukdee, R., and Sharma, D. Reliable learning in challenging environments. Advances in Neural Information Processing Systems, 36:48035- 48050, 2023b.
Ahmadi, S., Beyhaghi, H., Blum, A., and Naggita, K. Set- ting Fair Incentives to Maximize Improvement. In Pro- ceedings of the Symposium on Foundations of Responsi- ble Computing (FORC), 2023.
Becker, B. and Kohavi, R. Adult. https://oPTdoi: org/10 /1/ 24432/4442/// 1996.
Ashtiani, H., Pathak, V., and Urner, R. Adversarially robust learning with tolerance. In International Conference Algorithmic Learning Theory, pp. 115-135. PMLR, 2023.
Bloomfield, R. J. What Counts and What Gets Counted. Available at SSRN 2427 106, 2016.
Ashtiani, H., Pathak, V., and Urner, R. Simplifying Adver- sarially Robust PAC Learning with Tolerance. Confer- ence on Learning Theory (to appear). PMLR, 2025.
Blum, A. and Saless, D. Regularized Robustly Reliable Learners and Instance Targeted Attacks. arXiv preprint arXiv:2410. 10572, 2024.
Attias, I. and Hanneke, S. Adversarially robust PAC learn- ability of real-valued functions. In International Con- ference on Machine Learning, pp. 1 1172-1199. PMLR, 2023.
Braverman, M. and Garg, S. The Role of Randomness and Noise in Strategic Classification. In Proceedings of the Symposium on Foundations of Responsible Computing (FORC 2020), 2020
10

---

PAC Learning with Improvements
Brückner, M. and Scheffer, T. Stackelberg games for adver- sarial prediction problems. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discov- ery and Data Mining (KDD), pp. 547-555. Association for Computing Machinery, 2011.
Goldman, S. and Kearns, M. On the Complexity of Teaching.
Journal of Computer and System Sciences, 50(1):20-31, 1995.
Haghtalab, N., Immorlica, N., Lucier, B., and Wang. J. Maximizing Welfare with Incentive-Aware Evaluation Mechanisms. In Bessiere, C. (ed.), Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 160-166. International Joint Conferences on Artificial Intelligence Organization, 7 Main track.
Bshouty, N. H. and Burroughs, L. Maximizing Agree- ments with Sided Error with Applications to Heuris- tic Learning. Machine Learning, 59(1)999-223, 2005.
Chawla, N. V., Bowyer, K. W., Hall, L. O., and Kegelmeyer, W. P. SMOTE: synthetic minority over-sampling tech- nique, Journal of Artificial Intelligence Research, 16(1): 321-357, Jun 2002.
2020. doi: 10.24963/ 20200/23
Hardt, M., Megiddo, N., Papadimitriou, C., and Wootters, M. Strategic Classification. In Proceedings of the ACM Conference on Innovations in Theoretical Computer Sci- ence, pp. 111-122, 2016.
Chen, Y., Liu, Y., and Podimata, C. Learning strategy-aware linear classifiers. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA, 2020. Curran Associates Inc. ISBN 9781 1713899546.
Helmbold, D., Sloan, R., and Warmuth, M. K. Learning nested differences of intersection-closed concept classes, Machine Learning, (52):165-196 jun 1990.
Hendrickx, K., Perini, L., Van der Plas, D., Meert, W., and Davis, J. Machine learning with reject option: survey. Machine Learning, 103(5):003--311 10, mar 2024.
Cohen, J., Rosenfeld, E.,, and Kolter, Z. Certified Adversar- ial Robustness via Randomized Smoothing. International Conference on Machine Learning. 2019.
Hu, L., Immorlica, N., and Vaughan, J. W. The Disparate Effects of Strategic Manipulation. In Proceedings of the Conference Fairness, Accountabiliry; and Trans- parency, FAT* 19, pp. 259-268, New York, NY, USA, 2019. Association for Computing Machinery.
Cohen, L., Mansour, Y., Moran, S., and Shao, H. Learnabil- ity gaps of strategic classification. In The Thirty Seventh Annual Conference on Learning Theory, pp. 1223-1259. PMLR. 2024.
Cullina, D., Bhagoji, A. N., and Mittal, P. PAC-leaming in the presence of evasion adversaries. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 228-239, Red Hook, NY, USA, 2018. Curran Associates Inc.
Kalai, A. T., Kanade, V., and Mansour, Y. Reliable agnostic learning. Journal of Computer and System Sciences, 78 (5):1481-1495, Sep 2012.
Kleinberg. J. and Raghavan, M. How Do Classifiers Induce Agents to Invest Effort Strategically? ACM Trans. Econ. Comput., 8(4), Oct 2020.
Darnstädt, M. The optimal PAC bound for intersection- closed concept classes. Information Processing Letters, 115(4):458 461. 2015.
Le Quy, T., Roy, A., Iosifidis, V., Zhang, W., and Ntoutsi, E. A survey on datasets for fairness-awe aware machine learn- ing. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 12(3), 2022a.
Davies, D. L. and Bouldin, D. W. A Cluster Separation Measure. IEEE Trans. Pattern Anal. Mach. Intell., 1(2): 224 227, Feb 1979.
Le Quy, T., Roy, A., Iosifidis, V., Zhang, W., and Ntoutsi, Fairness datasets. https://githa: homm/tailequy/faireeeee http://aaannss_daaastttee//o www.dddatttttteeeee / (872600faaeaa7aaa111444444666663 2022b.
Dong, J., Roth, A., Schutzman, Z., Waggoner, B., and Wu, Z. S. Strategic Classification from Revealed Preferences. In Proceedings of the ACM Conference on Economics and Computation (EC), 2018
Sani,, R. and Wiener, Y. On the Foundations of Noise- free Selective Classification. Journal of Machine Learn- ing Research, 1653)1160--1641 2010.
Lechner, T. and Urner, R. Learning losses for strategic classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7337-7344, 2022.
Geifman, Y. and EI- Yaniv, R. Selective Classification for Deep Neural Networks. Proceedings of the s1 Inter- national Conference on Neural Information Processing Systems, 2017.
Madry, A., Makelov, A., Schmidt, L., Tsipras, D... and
Vladu, A. Towards Deep Learning Models Resistant to Adversarial Attacks. In International Conference on Learning Representations, 2018

---

PAC Learning with Improvements
Miller, J., Milli, S., and Hardt, M. Strategic Classification is Causal Modeling in Disguise. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6917-6926. PMLR, 13- 18 Jul 2020.
Shahapure, K. R. and Nicholas, C. Cluster Quality Analysis Using Silhouette Score. In 2020 IEEE 7th International Conference Data Science and Advanced Analytics (DSAA), pp. 747-748, 2020.
Shavit, Y., Edelman, B., and Axelrod, B. Causal Strategic Linear Regression. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference Ma- chine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8676-8686. PMLR, 13-18 Jul 2020.
Milli, S., Miller, J., Dragan, A. D., and Hardt, M. The Social Cost of Strategic Classification. In Proceedings of the Conference on Fairness, Accountability, and Trans- parency, pp. 230 239, 2019.
Montasser, O., Hanneke, S., and Srebro, N. VC Classes are Adversarially Robustly Learnable, but Only Improperly. In Beygelzimer. A. and Hsu, D. (eds.), Proceedings of the Thirty-Second Conference on Learning Theory, vol- ume 99 of Proceedings of Machine Learning Research, pp. 2512-2530. PMLR, 25-28 Jun 2019.
Sundaram, R., Vullikanti, A., Xu, H., and Yao, F. PAC- learning for strategic classification. The Journal of Ma- chine Learning Research, 24(1), Jan 2023.
Zhang, H. and Conitzer, V. Incentive-Aware PAC Learn- ing. Proceedings the AAAI Conference Artificial Intelligence, 35(6):5797-5804 May 2021.
Montasser, O., Hanneke, S., and Srebro, N. Reducing ad- versarially robust learning to non-robust PAC learning. Advances in Neural Information Processing Systems, 33: 14626-14637 2020.
Zmic T., Mazumdar, E.. Sastry, S., and Jordan, M. I. Who leads and who follows in strategic classification? In Proceedings of the 35th International Conference Neural Information P Processing Systems, NIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc.
Montasser. O., Hanneke, S., and Srebro, N. Adversari- ally robust learning with unknown perturbation sets. In Conference on Learning Theory, pp. 3452-3482. PMLR, 2021.
Natarajan, On learning boolean functions. In Proceed- ings of the nineteenth annual ACM symposium on Theory of computing (STOC), pp. 296-304, 1987.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cour- napeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine Learning in Python, Journal of Machine Learning Research, 12:2825-2830, 2011.
Perdomo, J., Zrnic, T., Mendler-Düinner, C., and Hardt,
M. Performative Prediction. In Proceedings of the 37th International Conference Machine Learning, pp. 7599- 7609, 2020.
Raman, V., Subedi, U., and Tewari, A. On proper learn- ability between average-ant and worst-case robustness. Ad- vances in Neural Information Processing Systems, 36:
13115-13126. 2023.
Rivest, L. and Sloan, R. Learning complicated concepts reliably and usefully. In Proceedings of the Seventh AAAI National Conference Artificial Intelligence, pp. 635- 640, 1988.
Rousseeuw, P. J. Silhouettes: A graphical aid to the in- terpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20:53-65, 1987.
12

---

PAC Learning with Improvements
A. Additional Related Work
Classification of gaming agents. Hardt et al. (2016) formalized the concept of strategic behavior, often referred to as "gaming," where test-set agents who are negatively classified intentionally modify their separable cost function-withour altering their target label, to deceive the model into classifying them as positive. They theoretically and empirically showed that their strategy-robust algorithm outperforms the standard SVM algorithm under gaming. However, as the extent of gaming increases, overall model accuracy declines. Dong et al. (2018) also study a Stackelberg equilibrium where agents strategically respond to classification learners. However, unlike Hardt et al. (2016), their model assumes that the learner lacks direct knowledge of the agents' utility functions and instead infers them through observed revealed preferences. Additionally, agents arrive sequentially, and only the true negatives strategically respond to the learner. The learner's objective to minimize the Stackelberg regret. Chen et al. (2020) also study a learner whose goal to minimize the Stackelberg regret, where gaming agents arrive sequentially. However, unlike Dong et al. (2018) which assumes convex loss function, they deal with less smooth agent utility function and learner loss function. They propose the Grinder algorithm, which adaptively partitions the learner's ' action space based on the agents' responses. Performative prediction (Perdomo et al., 2020) considers a setting that involves a repeated interaction between the classifier and the agents, and as a result the underlying distribution of the gaming agents may change over time.
the bounds of a
Classification of agents that can both game and improve. Unlike earlier works in the strategic classification literature, which primarily focus on settings where agents engage in gaming behavior, Kleinberg & Raghavan (2020) examine a scenario where agents can genuinely improve. In this context, the agent can modify their observable features and true label to achieve a positive model outcome. The authors demonstrate that a learner employing a linear mechanism can encourage rational agents, who optimize their allocation of effort, to prioritize actions that result in meaningful improvement. They show how achieve this by selecting an evaluation rule that incentivizes a desirable effort profile.
Ahmadi et al. (2022). like Kleinberg & Raghavan (2020), consider the agents' potentially truthful and actionable responses to the model. However, the primary objective of Ahmadi et al. (2022) is to maximize true positive classifications while minimizing false positives. Notably, for the linear case, they show that the resulting classifier can become non-convex, depending on the agents' initial positions.
On the other hand, Ahmadi al. (2023) design reachable sets of target levels such that they can incentivize effort-bounded agents within each group to improve optimally.
Theoretical guarantees of incentive-aware or incentive-compatible classifiers. Zhang & Conitzer (2021) show that the vanilla ERM principle fails under strategic manipulation (gaming), even in simple scenarios that would otherwise be straightforward without gaming. To address this, they propose the concepts of incentive-awar and incentive- compaiilee ERMs, theoretically analyzing the corresponding classifiers, their sample complexity, and the impact on learnability of the VC dimension of the concept hypothesis class. Finally, they extend their analysis to ERM-based learning in environments with transitive strategic manipulation.
Given adversarial data points wanting to receive an incorrect label, Cullina al. (2018) theoretically show that the sample complexity of PAC-learning set of halfspace classifiers does not increase in the presence of adversaries bounded by convex constraint sets and that the adversarial VC dimension can be arbitrarily larger or smaller than the standard VC dimension. Sundaram et al. (2023) provide theoretical guarantees for an offline. full-information strategic classification framework where data points have distinct preferences over classification outcomes (+ or -) and incur varying manipulation costs, modeled using mominorm-inducee cost functions. They propose a PAC-learning framework for strategic linear classifiers in this setting, providing detailed analysis of their statistical and computational learnability. Additionally, they extend the concept of the adversarial VC dimension (Cullina al., 2018) this strategic context. They also show, among other things, that employing randomized linear classifiers can substantially improve accuracy compared to deterministic methods.
Reliable machine learning. The concept of risk aversion in our work is closely related to selective classification or machine learning with reject option (EI- Yaniv & Wiener, 2010; Geifman & El- El-iv,,v, 2017: Hendrickx et al., 2024), where the classifier balances the trade-off between risk and coverage, opting to abstain from making predictions when it is likely to make mistakes Similarly, risk-averse classification aligns with aspects of learning with onc-sided error (Natarajan, 1987; Bshouty& & Burroughs, 2005), particularly positive reliable learners (Kalai et al., 2012), which aim to achieve zero false positive errors while minimizing false negatives. Prior work has shown connections between strategic classification and adversarial learning (e.g. Sundaram et al. 2023), but it remains an interesting open question if similar connections can be
13

---

PAC Learning with Improvements
established between learning with improvements and reliable learning in the presence of adversarial attacks (Balcan et al., 2022; 2023b; Blum & Saless, 2024).
Adversarial robustness. Our results indicate that the properties of the concept class that govern learnability with improvements are different from those established for adversarial robustness. In particular, 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 (Montasser et al., 2019). Furthermore, our risk-averse learning algorithm is very different from techniques proposed the adversarial literature, including robust Empirical Risk Minimization (Cullina et al., 2018; Attias al., 2022b), boosting algorithms whose generalization based on sample compression schemes (Montasser et al., 2019; 2020; Attias et al., 2022a; Attias & Hanneke, 2023) and approaches developed for neural networks (Madry al., 2018; Cohen et al., 2019; Balcan et al., 2023a). Similarly, our algorithm for learning halfspaces approaches for learning from malicious noise (Awasthi et al., 2013; Balcan & Haghtalab, 2020). 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- for example, extensions to unknown or uncertain improvement sets (Montasser et al., 2021; Lechner & Urner, 2022), and learning with tolerance (Ashtiani et al., 2023; Raman et al., 2023; Ashtiani et al., 2025).
unit ball differs from classical
B. Separating PAC Learning with Improvements from the Standard and Strategic PAC Models
Here, we further prove that learning with improvements diverges from the the behavior of the standard PAC model for binary classification, and also from the more recently studied PAC learning model for strategic classification (Hardt et al., 2016; Sundaram et al., 2023).
B.1. Separation from Standard PAC Learning Model when H. c H.
Example 3 (Error gap when the learner's 's hypothesis space H is a strict subset of the concept space H. that contains f*). Let X' == [-1, 1] and H denote the set of concepts including unions of up to k open intervals. The set of possible improvements for any point æ E X' is given by X n Q, where Q denotes the set of rational numbers. Suppose the data distribution is uniform over X. We set the target concept f" as follows
0, if Faa<0, Q
(')))
-
{1, otherwise,
Note that rationals are dense in [0. 1] and the of all rationals have a Lebesgue measure zero. Thus, on any finite sample S Xmm any sampled point will have a positive label according to f iff x 2 0 (with probability 1). In the standard PAC learning setting, the classifier f = 1fx E (0, 1)} achieves zero error w.r.t. the target f*. This is because the misclassification error for points in Q is zero.
In our setting where agents have the ability to improve, for an h E H which predicts any point x' in Q as positive, all negative agents in 1) can move to such a point x' and be falsely classified as positive. This corresponds to a lower bound on the error. Since rationals are dense in the reals, any open interval which h classifies as positive must contain a point in Q On the other hand, if classifies no point as positive, then error rate is again Y/2 as all the positive points are misclassified.
B.2. Comparison with the PAC Model for Strategic Classification
We first observe that the strategic classification loss can be obtained by a subtle modification our loss function (1),
Loss STR LEs
max of 2')
(2') fx)).
Intuitively, for a negative point with (x) O, (x) here denotes the set of points that the agent x can "pretend" to be in order to potentially deceive the classifier into incorrectly classifying the agent positive. Since the movement within (x())
is viewed as manipulation by the agent x, the prediction on the strategically perturbed point is compared with the original label of x, i.e. (x)
14

---

PAC Learning with Improvements
Prior work has shown that learnability in the strategic classification setting is captured by the strategic VC dimension (SVC) introduced by Sundaram et al. (2023). We state below the definition of SVC, adapted our improvement-set based setting above which is special case of the general cost functions studied under the strategic classification setting.
Definition B.1 (Strategic VC dimension, Sundaram et al. 2023). Define the n-th shattering coefficient of strategic classification problem as
On (H, = max ((h(2))....,a(()) : H. E (z,))) (x)
Then SVC(H, A) = sup(n 20: on, 2
natural question to ask is whether learning with improvements is "easier" than strategic classification. That is, if a concept space H is learnable w.r.t. A and D in the strategic classification setting, then is it also learnable with improvements? Interestingly, we answer this question in the negative. More precisely, we show that finite SVC (which is known from prior work to be sufficient condition for strategic PAC learning) is actually not a sufficient condition for PAC learnability with improvements.
Theorem B.2. Finite strategic VC dimension (Sundaram et al., 2023) does not necessarily imply PAC learnability with improvemenss.
Proof. Let the instance space X' be [0, 1J. let H = {habed habed (2) = 1 iff æ E [a, b) U (c, d]} and let D be the uniform distribution over [o. 1]. We define A as follows. For x E (0,3 )) let A(x) = B(x, 1/4) = (x 1/4, x + 1/4) n [o, 1]: for x E [3/4, 1]. let (ar) = {a].
We claim that no algorithm with finite training data can guarantee an expected error of less than 1/16 for the above when learning with improvements, even though the class is PAC-learnable in the strategic classification setting. To see the latter, note that SVC(H, A) < 4. Indeed, consider the points (0, 1/4, 1/2, E 2 Notice the (strategic) labeling 1,00, 1) cannot be achieved for any h E H. which establishes the claim.
Now consider a target function defined as the union of two intervals [1/2, b) U (b, 1] where the number was randomly chosen in [3/4, 1]. The learner will not see the point b given a finite training set, so it learns nothing about the location of b (almost surely). Now, we consider two cases. Either, the learner outputs a classifier whose positive region has probability mass most 1 161 over the interval /3/4, 7/8). Then its error rate is least 1/16 because the positive examples in [3/4,7/8 7/8) cannot move so at least half of their probability mass will get misclassified. On the other hand, if the learner outputs classifier whose positive region has probability mass greater than 1/16 on the interval [3/4, 7 7/8), then it has at least a 50% chance of including the negative point b in its positive region (over the random choice of the target function). If the classifier has a negative point in [3/4, 4, 7 7/8] that is incorrectly predicted to be positive, then it will have an error rate at least 1/16, because all the positives in [5/8, 3/4) will move to false positive (here we use that agents break ties adversarially, see also Remark 2). So, either way, its expected error is 2 1/16.
On the other hand, it is not too hard to come up with examples where it easier to learn in the improvements setting when compared to the strategic setting. Example 4 shows that it is possible to learn perfectly with improvements (with zero error) in setting where avoiding large constant error is unavoidable in the strategic classification setting.
Example 4 (Learnability with improvements may be easier than strategic classification). Define A(x) = X for all examples J E X. Suppose the "all-negative" classifier h- (x) = 0, the "all-positive" classifier (x) = 1, and all siingleton-postivve classifiers hn- (x) = I| x²] lie in the concept space H. Select any f" E H and any data distribution D over X' such that PawDIf (x) = 0j = PE-DDf
1] = Now with O(log })) examples, the learner sees positive example, say x+, in its training set with probability 8. Outputting hu+ achieves zero-error in the learning with improvements setting, as all negative points can improve to . In contrast, a learner in the strategic classification setting must suffer an error of at least 1/2 here. Indeed, either the learner outputs h- and suffers an error of 1/2 on the positive points. Or, the learner selects an h that labels at least one point as positive and incurs an error 1/2 on the negative points, all of which successfully deceive the learner.
Furthermore, let's consider an improvement function A that takes into account f*, such that f* = 1 for x' E A(x) for any x E X. That is the improvement function is in a certain sense consistent with f", guaranteeing positive classification after any move. In this setting, any classifier h will have lower error in the improvements setting compared to strategic classification. This is because negative point that moves and becomes positive is an error in strategic learning but the point
15

---

PAC Learning with Improvements
would have genuinely improved in this case. Contrasting this with Remark 2.1, when A does not satisfy the above property, note that the reason it is possible do worse in the improvement setting (e.g. Theorem B.2) is because some positive examples can potentially become negative when moving in response false positive for the learner's hypothesis h.
C. Missing Proofs from Section 4
include below missing proofs from Section
C.1. Proof of Theorem 4.1: Learning Thresholds with the Uniform Distribution
Proof. Let iid. Dm,, where D the uniform distribution over [0, 1]. By using a standard calculation of the sample complexity of thresholds.
P 1/-- (x) + his (x) >
5 P [x 10", ec]
Sm2m LonD
< (1 m
< -em
K 6,
where the last inequality holds for 2 log 3. Since whenever hgg classifies point positive, h4- also classifies it positive, any negative point that improves in response to hs+ must move true positive point, and the error only decrease in the improvements setting for the choice of hg+
Now, since we allow improvements of distance r, the points in the interval [4s+ - r, As+] that would have heen classified negatively without improvement are able to improve under hgg (and indeed improve to be positive with respect to he and are thus classified correctly. The points on which hs+ makes mistakes are those in the interval [t", tst r]. Since D is uniform, previous inequality implies that with probability at least 1 we have 1s+ t This implies the that error is most max(c r, 0) with probability 1 8 as desired.
C.2. Learning Thresholds with An Arbitrary Distribution
Theorem C.1 (Thresholds, arbitrary distribution). Let the improvement set A be the closed ball with radius A A(z) {xl - - x'1 < r). For any distribution D, and any c, 5 E 1/2), with probability 1 8,
Lossp(hgt,hyp hr-) (E p(hs+: : (Dr))
where
(hes: PAND (xr E [ts r,ts:))
with sample complexity M = 0 log 4
Proof. Let to be such that IP PDDD (or [t*, toll e. By following the same derivation in Eqn. and replacing t with to, get that
PP SwD
P... LEWD
[hr (x) o hig (x) se).
(x)
with probability for m 2 log 1
The points in the interval [t.+ r, + are able to improve under hs+ and thus classified correctly. The gain to the error of fist would be the probability mass of points in D that fall into this interval, defined as
p(hsi br D,r) PAND far [tst r, tst ]].
16

---

PAC Learning with Improvements
The points which li+t makes mistakes are those in the interval [L* 1--- - r).
We conclude that with probability at least å we have t S to. and given the improvement of points in [t" ,ts we have an error at most max(c - p(hs+: he- D)r), 0) with probability ô as desired.
C.3. Proof of Theorem 4.6
Proof. Let Rg CLOSH... (fz; E S: y: = 1}} be the output of the closure algorithm. For the standard PAC setting, we have
P S-m
P L
(x)
+ R (x)))) = c]
with probability 5 for m 2 Q (2 (d+ log 2)), see Darnstädt (2015). Since whenever R's classifies a point as positive, also classifies as positive, any negative point that improves response to R& must move to a true positive point and the enror can only decrease in the improvements setting for the choice of Rg..
Now, in order to quantify the gain in enror from the improvements, define the "outer boundary strip" of R's. Let the rectangle defined by Rg Il la;, b.j. The points that are able to improve under Itg are exactly fall into the outer boundary strip of size defined as
BS(
II (E|d]
[as + by +r] \ II
[as, by].
kE|d]
Note that this is exactly the improvement region of Rg: BS( = (R; R' A). Under general distribution D, the probability mass of the improvement region is
PAND [a E IR(RS; A)] PDwD [a E BS(RS, r)],
since Rs is the smallest rectangle that fits S, these points that are able to improve under It.. indeed improve to be positive with respect to R. This implies that
Lossp(RG, R*) < max (E -
(a-Pa-D PawD (o E IR(RS: R", ()))
Now, for the uniform distribution, we can compute an exact expression of the improvement region. Let 1; = b; a,, then
PADD BaDDgEEI(RRGFF IR(R;; R A) = II
(4 + 2r)
II 4. <E(d]
<E(d]
For = 2, we get
PAND (R(; R*, A)] (4 + 2r2 + 2r) 1122
2r(4 + 12) + 4r
C.4. Proof of Theorem 4.7
Proof. Let 5 ~ T and h3 denote the classifier learned by the closure algorithm (Definition 4.4). For some m O (H) + log })), we know from prior work (Auer & Ortner, 2007; Darnstädt, 2015) that hG satisfies, with probability at least 8,
P PAND + (*)) <
for any target concept f E H.
17

---

PAC Learning with Improvements
(1) + [x))] = since Ang (+) (x) Now for any x X (z) the improvement loss Loss(1;; /²) [*)
0 and if Ang (2) * {0), for any point 1 = (x') and therefore Loss(2;; kG, f*) O. So the only points for which h can make a mistake are points where (z) = 0 and Ang (z) = {Ø), i.e. the points do not move in reaction to hg. This implies hg must disagree with f on these points also in the PAC setting. But the probability mass of these points is at most as noted above.
and (x) 1 since h is obtained using the closure algorithm. If hg
r Ang we have hg
C.5. Proof of Theorem 4.8
Proof. For any concept h E H. let X denote the set of points {ar E X' h(x)) = 1} positively classified by h. Since H' := H. Ixyfa') is not intersection-closed there must exist a set S _ X \ {x'} such that CLOSH (5) & H'. For the uniformly negative point x', we have its improvement set as A (z') = X \ For points in CLOS(S) we have the improvement set as the empty set. We set the data distribution D as the uniform distribution over CLOS(S) {z'}. Let hi E H be a minimally consistent classifier w.r.t. S, i.e. if h E H and X S x then N'' h4 By choice of S, there is a point 21 E X CL (S). By the definition of closure of S, there must exist h2 E H. consistent with S (assumed minimally consistent WL.OG) such that (21) = O. Also, since hyj was chosen to be minimally consistent, there must exist T2 E X such that b (x2) O. We will set the target concept f to one of h1 or h2.
Now any learner that picks concept not consistent with S will clearly suffer a constant error on the points in CLOS(S) which are incorrectly classified as negative and not allowed to improve. Suppose therefore that the learner selects a hypothesis h consistent with S. Let h denote a classifier which is minimally consistent with S and x+ S xx (h could possibly be the same as h). If h = h1 (resp. h = h22, the learner suffers a constant error as x' can improve to the false positive #i (resp. x22 when the target concept is h2 (resp. h1). Else, there must exist 5 E xx* such that hı (ō) = 0, since hi was chosen to be minimally consistent (and likewise for f2). h(ā)= in this case, and x' can now falsely "improve" to ă. Since the learner has no way of knowing from the sample whether the target is h2 or h2, it must suffer a constant error for any h selects from H.
D. Missing Proofs and Additional Definitions from Section 5
We include below additional definitions and complete proofs for results in Section 5.
D.1. Additional Definitions
Definition D.1. The shortest path metric de: : V x V - |0. [I [V]+)) is defined as follows:
x') = min [kl 3 (xm = .I....... Us = x') V. (x)-1, E E [K], if a path exists,
[V + 1,
if path exists.
Here, l is the length of the shortest path between x and x in terms of the number of edges. If there is no path connecting x and x', the distance is defined as [V| [|++1 1. The shortest path metric satisfies the following properties:
Non-negativity: do(a,==)) 2 0 for all x, E V, with do(x, x)) O. Symmetry: da(a, = da .)) for all x, xf E V, since G is undirected.
Triangle inequality: dz(2z, x²) S do(x, 2) + x') for all 2, 2', V.
Our results in Section 5 extend to the more general improvement function A(x) = {x' E V dz) by applying our arguments to G", the rth power of G.
Definition D.2 (Dominating Set). Let G = (V, E' be an undirected graph, where V is the set of vertices and E C V x V the set of edges. A subset of vertices S C V is called a dominating set if every vertex in V is either in S or adjacent to at least one vertex in S. Formally, S is dominating set if:
Ya E V, x E S or Fr E S such that (2, E E.
18

---

PAC Learning with Improvements
D.2. Proof of Theorem 5.1
Proof. Given a sample S labeled by f", let S+ = far (()) +1} denote the set of positive points in S. To achieve the claimed upper bound on the sample complexity of learning with zero-error, the learner outputs hg with hz(2) = 1[x St}, that is the classifier which positively classifies exactly the points in St We will now show that with millog++lin +log $1 the proposed lig achieves zero generalization error with probability at least 1 8. d +1
sample of size O
Let V+ = f (z) +1} denote the set of vertices in G+, We say that V is covered by the sample $ if E S or there exists x' E S such that x' E V+ and (x,,x") E. Note that if every x E V is covered by S, then Lossp(hs, _*) = O (formally established in Theorem 5.2). It is therefore sufficiently to bound determine the sample size needed to guarantee that every positive vertex is covered with high probability.
Let V+ be a vertex the positive subgraph G For x to be covered, must either be included in the sample S, or have least one of its neighbors x' [(z) included in S The probability of sampling r directly in one draw is 1. The probability of sampling any of its neighbors is proportional to its degree in G+, Thus, the total probability of covering in one draw is:
n²
Peover (I) .(1 d(x)),
n
where d(x:) is the degree of x in
Since d(x) 2 d we have:
mmin +
Peaver (xr
n
To ensure the desired coverage holds with probability at least 5, we analyze the failure probability for a single vertex. The probability that given vertex E V+ is not covered after m samples is
dmin + (1-"min
m
P|r is not covered] s
n2
To ensure that this holds for all |V+| < n vertices, we apply the union bound
min (1-
d+ + 1
P[Er E V+ not covered| S
n2
Therefore, the sample size required to ensure that the probability of the above bad event is at most 8 is given by
d (m(l
nnllogn n log 4
m = m=
To establish the lower bound, consider graph G on vertices consisting of k disjoint cliques, each of the same size d + 1, see Figure 3. Now note that if our sample S does not contain any node from any one of the cliques (say C), then zero-error is not possible. This is because, one of two cases occur. If the learner's hypothesis h predicts any point in C as positive then we can select an f that predicts entirely as negative while being consistent with S, causing the population loss to be at least }. On the other hand, if the learned predicts all points in C as negative, then we can set f to label C' entirely as positive, again incurring a population loss of least 1
Our goal therefore is determine lower bound the number of points required ensure that every clique has least one of its vertices included in the training sample S, which ensures that for every positive vertex, either the vertex itself or one of its neighbors is included. Using the standard coupon collector analysis, the number of trials needed to collect k n coupons is Q(k log k) with high constant probability.
19

---

over the draw of S. Moreover, there exists a graph G for which any labeled points in PAC Learning with Improvements
Figure 3. The graph G' used to establish our lower bound on the zero-error sample complexity. The graph consists of k components, each size E-
D.3. Enabling Improvement Whenever Helps
Theorem D.3. Let = EV be an undirected graph with n = [V| vertices, and let f VV - (0,+1) denote the ground truth labeling function. Define: V+ = for V (x) = +1}, the set of positive vertices. Define V- {a E (x) 0} the set of negative vertices, and N {ar E V 13x' E V+ such that (x, x') Σ} denote the of negative vertices that have a positive neighbor. Let d mingEN H EV+ (x. ) E}| denote the minimum number of positive neighbors of vertices in N. Assume that the data distribution D is uniform on V. For any 5 >> 0, and training sample S itd. DDm of size m = O n+oog b)) there exists a learner that oulputs a hypothesis such that Loss f*) = 0, with probability at least ami
learner that always outputs with Loss (*) the training sample, with high constant probability.
(+) =
for any D must see least Q log d
Proof. The proof of the upper bound is technically similar to the proof of Theorem 5.1. Essentially, ensure that Loss 0, we need to cover all the vertices in N by some vertices in V+, The probability that any fixed node in N is covered by random sample can be lower-bounded in terms of d.V. as
Auin n
Peover (x)
Using the same argument as Theorem 5.1, we obtain an upper bound of m = O [n(ogg n log })
on the sample complexity of the classifier h which outputs exactly the positively labeled points in its sample as positive to guarantec that Loss f*) with probability least 1 5.
d
To establish the lower bound, consider graph G = (V, E) with two types of nodes, i.e. V = V/ 1V/2,VV/=1 -V f labels all nodes in V1 as negative. Each node z; V1 has d = n-k neighboring nodes A; in [Vg] and the sets of these k
|V n-k
neighbors are pairwise disjoint. Now, suppose our training sample S does not contain any point in A; for some E [k:] If the learned hypothesis h predicts any point A as positive, we have hxxx)) + {ar} but if f labels all points in A, negative, (*(x)) {a,} and we incur loss corresponding to di. Similarly, if h labels points in A, as negative then h(x;)) = (a.) but we can label A, consistent with S such that (xx) A {x.).
Pigure 4. The graph G used to establish our lower bound in Theorem D.3.
Therefore it is sufficient determine lower bound on the number of points required ensure that every A has least one of its vertices included in the training sample S. Using the standard coupon collector analysis, the number of trials needed to collect k TN +I coupons is (2 log k) with high constant probability.
20

---

PAC Learning with Improvements
Theorem D.4. Let G EV,E) be an undirected graph with [V] vertices, and let f" V {0,+1} denote the ground truth labeling function. Define V {ar V (x) = +1}, the set of positive verfices and d denote the minimum degree of a vertex in V+ in the subgraph of G induced by V+. Define V {z E V f*(x) 0}
the set of negative vertices, and N = & VV Bx' E V such that (x, x!) E E} denote the set of negative vertices that have a positive neighhor. Let d = mingen Ka' E V+ (xr, E E.] denote the minimum number of positive neighbors of vertices in N. Assume that the data distribution D uniform on V. For any 6 > O, and training sample S 1td DD of size = 0 n:llg n+log +) there exists learner that outputs a hypothesis h such that Lossp(h, f*) = and (h,
minqd Shinn
O, with probability at least 6 over the draw of S. Moreover, there exists a graph G for 0 for any D, f must see least AN 1) labeled points in the training sample, with high constant probability.
which any learner that always oulputs with LOsSp (h, Lh,
Ω maxf min
log
log
d
amin
Proof. See Theorems 5.1 and D.3.
D.4. Proof of Theorem 5.2: Teaching a Risk-averse Student
Proof. Since S is dominating set of G+ (V+ ), for any V+, either S* there exists x' E S+ such that (x, E+ In the first case, hg- (æ)) = 1 and therefore Ang (x) {x}. Thus, hgt (z) 1 f (z) implies that
Loss(æ; hs+, (*) = 0 in this case. In the second case, St, but there exists a neighbor Ā E (xx) such that ă E S+
by the definition of S Thus, for any point x' E Angt (x) C St, we have that hS (x') = 1 f (x"), ensuring that
Loss(2; hst, f f*) = 0 in this case as well.
For E VVVVA V+, x has no positive neighbors St, Angt (x) = {ar because there is no neighhoring vertex x' E A(x) that would induce a reaction. Thus, hşt (x)
(x) this case, implying the loss Loss( hsi ff' on is zero
Finally, i E V V* has positive neighbors contained in the dominating set, i.e., A(x) # 0. then hg+ (α') +1. The
reaction set Ah g ensures that moves to one of these neighbors. Specifically, the reaction set allows to improve and move to a neighboring vertex x' E Aax) n n* such that (xx) = +1. Thus, h(x²) (x') = +1 for any x' E Ang (r) implying Loss( h O.
21

---

PAC Learning with Improvements
E. Evaluation: Supplementary Details
This section includes supplementary details on the datasets and classifiers used, how improvement is done and results the empirical evaluations.
E.1. Datasets
We utilize three real-world datasets: the Adult Income dataset from UCI and the Open University Learning Analytics Dataset (OULAD) and Law School datasets sourced from Le Quy et al. (Le Quy al., 2022b). The preprocessing steps for all the datasets, similar to those described in Le Quy al. (Le Quy et al., 2022b), include removing missing data and applying label encoding categorical variables. In addition to the real-world datasets, generate 8-dimensional synthetic dataset with increased separability (class_sep= 4) using the make_classtte classsilassiic function from Scikit-leam. We clean the dataset by removing duplicates and outliers, with Z-scores applied with thresholds (0.9 for class O and 0.8 for class 1). The cleaned synthetic dataset is then balanced using SMOTE (Chawla et al., 2002) to ensure class balance.
Statistical details of the datasets, including test/train sizes and number features, are in Table 1. examine the structural variations within datasets gain deeper insights into how the characteristics influence the impact of improvements on error drop rates. Figure 5 highlights the target distribution across training datasets: the Adult dataset has higher proportion of negative examples, whereas the OULAD and Law School datasets have higher percentage of positive examples. The synthetic dataset, by contrast, is balanced. Figure 6 and 7 illustrate dataset separabilityy properties, showing that the synthetic dataset (k-NN error: 0.1016) and the Law School dataset (k-NN error: 0.1010) have the highest separability. However, as Figure shows, the Adult and synthetic datasets exhibit the lowest false positive (FP) outlier rates.
Dataset
Target variable
d
Train/Test
Improvable features
Adult
{1(> 50K), 0(5 50K)}
14
21113/9049
{ weouus-per-week. capital-gain, capital- loss, fnlwgt, educational-num, workclass, education, occupation") {"code module, imd num of www.ppeev.aae prev.attempts, studied.creditt") { Ib decile3, Isat, ugpa, zfygpa, zgpa, fulltime, fam inc, tier") (all features are used]
OULAD
{ (pass), O(fail))
11
15093/6469
code presentation, highest.education,
Law school
{1 (pass), ((fail)
11
14558/ 14558/6240 /6240
Synthetic
{1(positive), ((negative))
1561/669
Table Details of the tabular datasets, both synthetic and real, used in the experiments.
800
49.2%
50.8%
15000
10000
12500
10000
600
Count
10000
Count
6000
Count
7500
Count
$1.8%
400
24.8%
4000
5000
5000
200
2000
2500
11.1%
0
>50K
$50K
Pass
Fall
Pass
Fall resulta
Positive
Negative
Final result
Target variable
Adult
(b) OULAD
(c) Law School
(d) Synthetic
Figure 5. Target variable distributions of synthetic and real-world train datasets used in the experiments for the ((a) Adult, ((b) OULAD, ((c) Law School, and ((d) Synthetic datasets.
22

---

PAC Learning with Improvements
Davies-Bouldin Index (lower is better)
Silhouette Score (1 is ideal, -1 is worst)
12.5
0.15
Davies-Bouldin Index
Silhouette Score
10.0
0.10
7.5
5.0
0.05
2.5
0.0
0.00
Adult OULAD
Law
Synthetic
Adult
OULAD
Law
Synthetic
Figure 6. Inspection of clusteredness and class separation using Davies-Bouldin index (Davies & Bouldin, 1979) and Silhouettes scores (Roussceuw, 1987; Shahapure & Nicholas, 2020).
Positive (Rrata)
False Negatives (Mee) False Pasitives (Atest
Negative (Nhwa)
False Negatives (Xte))
Negative (Xran)
Positive (Ahatt)
False Positives (Ahesl
Principal component
Princ pal component
-2.5
2.5 Principal component
5.0
7.5
Principal component
(a) Adult
(b) OULAD
Positive (Aran)
False Negatives (Nime)
Positive (Nira)) Negative (How))
False Negatives (Xuw))
Negative (Rran)
False Positives (Atme)
Principal component
Principal component
0-
-5.0
-2.5
2.5
Principal component
Principal component 1
Law school
Synthetic
Figure 7. Scatter plots of the two principal components of the training data and of the k-NN misclassification on test data for the ((a))
Adult (l-NN error: 0.1670. FNR: 0.4610, FPR: 0.0678), ((b)) OULAD (k-NN enror 0.3291, FNR: 0.19 FPR: 0.7645), ((c) Law
School (k-NN error: 0. 1010, FNR: 0.0180, FPR: 0.7875), and ((d) Synthetic (f-NN error: 0. 1016, FNR: 0. 1960, FPR: 0.000) datasets.
23

---

PAC Learning with Improvements
Dataset
DTC1
DTC2
RFC1
RFC2
XGB
Adult
0.999967 1: 0.0000499
0.999967 + 0.000049
0.999934 1 0.000079
0.999967 0.000049
0.999967 0.000049
Law
1.000000 + 0.000000
1.000000 = 0.000000
1.000000 + 0.000000
1.000000 + 0.000000
0.999952 + 0.000071
OULAD
1.000000 + 0.000000
1.000000 + --.000000
1.000000 = 0.000000
1.000000 + 0.000000
1.000000 + 0.000000
Synthetic
1.000000 + 000000000 1.000000 = 0.0000000 1.000000 = 0.000000 1.000000 + 0.000000 1.000000 + 0.000000
Table 2, Accuracy score of the f" models when trained and tested on Sr across different datasets.
Dataset
DTCI (LO0)
DTC2 (LOO)
RFCI (LO0)
RFC2 (LOO)
XGB (LOO)
Adult
0.8084 + 0.0044
0.8053 0.0045
0,8541 0.0040
0.8545 + 0.0040
Law
0.8507 + 0.0048
0.8428 + 0.0049
0.8962 + 0.0041
0.8972 + 0.0041
0.8894 = 0.0043
OULAD
0.5941 + 0.0066
0.5932 + 0.0066
0.6684 + 0.00663
0.6689 + 0.0063
Synthetic
0.9955 + 0.0028 0.9951 + 0.0029
0.9969 + 0.0023
0.9973 + 0.0021
0.9955 = 0.0028
Table Average leave one out (I.OO) score the f models on Sr across different datasets.
E.2. Classifiers
In all experiments set the random seed 42 to ensure reproducibility and consistency across all runs. All experiments conducted on a laptop computer with the following hardware specifications: 2.6-GHz 6-Core Intel Core i7 processor, 16 GB of 2400-MHz DDR4 RAM, and an Intel UHD Graphics 630 graphics card with 1536 MB of memory. Below are supplementary details about the classification models used. Below are supplementary details about the classification models used.
E. THE f" MODEL
The function f* served as the ground truth labeler, assessing whether the agent's modifications led a successful improvement. We evaluated five standard machine learning binary classification models, each achieving near 100% accuracy when trained and tested on ST (see Table 2). These models include two decision tree classifiers (DTC1 and DTC2), two random forest classifiers (RFCI and RFC2), and a gradient boosting classifier (XGB). Descriptions of these models are provided below.
1. Model fi (DTCI): A decision tree classifier with the following hyperparameters: criterion "'ettrpy",, samplesslls 2, min maipleampes__eaa leaf = 1, and random_state 42.
2. Model f (DTC2): A decision tree classifier with the following hyperparameters: criterion "gini", min_mmnnmma sein__smpleessppp
= 2, min_samples_lea leaf = 1, and handom_state = 42.
3. Model fī (RFCI): random forest classifier with default settings and random_stade state 42.
4. Model fi (RFC2): A random forest classifier with the following hyperparametens n_estimators 500, min.samples.split min_samples.leaf max featuurss = "sqit", bootstrap True, oob_score True, and ran- dom_state = 42.
5. Model f (XGB): A gradient boosting classifier with the following hyperparameters: n esesimmttors = 500, max depth 50, learning rate = 0.088, min_child weigd = 2, subsample=0.9, gamma = 0.088, and random_star state = 42.
We define the ground truth labeler f* either as a singular n0ar- accuracy model (see Table 2) or as agreement among multiple ncar-100% accuracy models.
The multi-defined I' model. Although the five f* models described above achieve nearly 100% accuracy when trained and tested on Sy, we assessed their generalization using the leave-one-out (LOO) validation score. The observed differences in LOO validation scores (Table 3), despite similar and high accuracy scores (Table 2), highlight potential generalization gaps. To account for this, we employ a multi-defined f* model to validate the experimental results.
24

---

PAC Learning with Improvements
For given data point 2, the five models: (1)) (x) and (x) each make prediction for the label of the data point. Based on these predictions, define boolean agreement mask M(x) that checks whether all four models agree on the prediction:
(x) = ((f((=) = f((z) - fz()) - (2) = (z))
where (.) is the indicator function that outputs all four models agree, and 0 otherwise. Using this agreement mask, we define the ground truth labeling function (x) as follows:
fi),, 0,
if M() - (i.c., full agreement)
(x)
(8)
otherwise
The singularly-defined f* model. Alternatively, we define the labeling function f*(x) using a single near-100%) accuracy model trained and tested on Sr, selected from the {S1 (Ir), [2 (1),, (a)), fi (v), Jī (a)). Unless otherwise stated, all experimental results were obtained using the DTC2 model (f2 (2:) the designated singularly-defined (1:) function.
E.2.2. THE DECISION-MAKER 'S MODEL (h)
We trained two-layer neural networks, denoted as h functions, using PyTorch with Adam optimizer with a learning rate of 0.001 and batch size of 64. These h functions generate decisions for the test set agents. In cases where the test agent receives a negative classification, they can, if within budget, improve their feature values to get the desired classification from the function. Table 4 summarizes the performance metrics of the f* and h model functions, demonstrating their varied performance across the datasets.
Since the empirical setup evaluates the impact of improvement on h's error drop rates, vary the loss functions train the model h function with. We use the standard binary cross entropy loss (BCE) and the risk-averse weighted- BCCt (wBCE) loss functions defined in Equation 5. In particular, because only negatively classified test-set agents improve, improvement (x'), if successful (that is, [xx) = h(x') ) = 1) reduces the false negative rate and turns true negatives into true positives. On the other hand, when unsuccessful (that is, (xx)
and h(2') = 1), it increases the false positive rate by turning true negatives into false positives and false negatives into false positives.
The model trained with the weighted-BCC BCE loss corresponds to (FP) errors more heavily than the false negative (FN) one, creating more compact positive agreement region that ensures more successful improvements. We prioritize minimizing FPs by ensuring the false positive to false negative weight ratio 141 = 4400 for the adult dataset. Another form of risk-averse classification we consider whe > is high, for example, 0.00I
risk-averse classifier that penalizes the false positive
only classifying an agent as positive iff the probability of being positive is high. That to say, we use the standard threshold 0.5 for the standard classifier and a higher threshold 0.9 for more risk-averse classifier.
Dataset
Model (kind)
Accuracy
Precision
Recall
F1 Score
Adult
2-layer neural network (h(x))
0.841087
0.699811
0.647677
0.672736
Law
2-layer neural network (h(x))
0.901282
0.911691
0.984731
0.946805
OULAD
2-layer neural network (h(z))
0.678003
0.698609
0.919853
0.794109
Synthetic
2-layer neural network (h(z))
0.994021
1.000000
0.988473
0.994203
Table Average performance of the standard models functions across different datasets' test sets Seet when test-sct agent cannot improve that is, r 0.
25

---

PAC Learning with Improvements
E.3. Agents Improvement
Given the feature vector of negatively classified test-set agent, Zorig and it's negative label (xorgg) the loss function C (BCE or wBCE), improvement budget r, step size a, number of iterations T and set of indices of improvement features S. compute the agent's improvement features. For each dataset, predefine the improvable features that the agents can change in order to get desirable (positive) model outcome (see Table 1). We vary the improvement budget in the empirical setup to so as to assess the impact of improvement on the the error drop rates.
Below are the steps of the improvement algorithm we used to compute each agent's improvement features.
Initialization:
F((0)
Forig
Iterative updates: Fort 0, O,.....,TT
1. Compute the gradient of the loss L with respect to the agent's updates a(0)²
g(e) = Vale, ((((
2. Update the improvement features by taking a step in the direction of the sign of the gradient:
a sign(g(o)i)),, i S
Pio
vi [d]
0,
otherwise
(((1)) ( + P())
3. Project the updated improvement features back onto the r-ball around the original features Torig
((+1)) = (Iorig + cirp =oorg))
Improvement vector: After T iterations, the final agent's improvement is given by:
=xxpp m'm
26

---

PAC Learning with Improvements
E.4. Evaluation Results: Supplementary Details
Following the key insights mentioned in the main paper in Section 6, below are the detailed observations from the experimental evaluation and the supplementary figures of the experimental results.
Effect of dataset characteristics. For all datasets consider, Figure 2 shows that the improvement budget increases, emror rates drop significantly, particularly when agents improve in response to risk-averse model trained using the LWRCF loss function. Dataset characteristics notably influence performance. For instance, as shown in Figure 6, the Law school and Synthetic datasets exhibit the highest separability and require relatively less risk aversion to achieve substantial and close to zero error reductions. Among all datasets, the Synthetic dataset shows a sharper error decline, reaching zero as the improvement budget increases (refer to Figure 2). Furthermore, as depicted in Figure 7, the Adult and Synthetic datasets demonstrate the lowest k-NN lest-set false positive rates (FPRs) of 0.0678 and 0.000, respectively, compared to the OULAD and Law School datasets. As seen in Figure 2, for both datasets, the error drops close to 0 as increases.
Effect of risk-aversion and improvement budget. Figures 10a, 10c, 10e and 10g show that when agents improve to risk-averse model trained using LWACE with "H > 1. the error rate decreases rapidly, particularly as the improvement was
budget increases. Notably, the higher the false positive to false negative weight ratio Wr, the faster the reduction in error wpg
(see Figure 8). In contrast, models trained with the standard LECE loss function exhibit a slower error reduction rate, almost looking like a line, under the same conditions as the effects of improvement are minimal and cancel each other out (see Figure 9).
Furthermore, the false negative rate (FNR) decreases as the improvement budget grows when the agents respond (improve) to an trace-trained model (see Figures 9b, 9d, and 9f). This is because almost 100% of the false negatively classified agents improve to become true positives as shown in Figures 9a, 9c, and 9e. On the other hand, on datasets where the weighted- BCE loss function effectively removed false positives (close to 0 false positive rate (FPR) before agents' improvement, remains very low, in some cases close to 0 (e.g., in Figure 9f), since no or few agents become false positives after improvement (see Figure 9c). However, when the weighted-BCC BCC loss function wasn't 't as effective, the false positive rate increases as the improvement budget 2.0 grows (see Figure 9d).
Although we observe similar trends when the threshold for classifying agent as positive increases 0.9 (instead of 0.5), the error is slightly higher and the reduction becomes slower (Figure 10). Additionally, while Figures 2 and 8 demonstrate diminishing returns for r > 2.0, different trend emerges in Figures 10b, 10d, 10f and 10h where we classify agents positive with high probability (0.9).
Effect of choice of f* model. Although different f models achieved ~ 100% accuracy on a given dataset while exhibiting varied LOO accuracy (cf. Tables and 3), the error drop rate showed consistent patterns when different f models are used. As shown in Figure 11, although some f models, such as RFC2 (fi) (ef. Figure 1cc), had higher performance gains than others, in all cases, the error drops rapidly as improvement budget increases and agents respond (improve) to BBCE-trained models.
Additionally, performance gains observed with evaluation of successful improvement using the multi-defined f (cf. Figure 12) were quite similar in trend and gains to those when singularly-defined model function f = f2 was used (cf. Figure 10, column one ((a), (c), (e) and (g))).
Our results indicate that while the f* models achieve ~ 100% accuracy when trained and tested on the unsplit dataset Sr, they often overfit, as shown by the LOO scores (cf. Table 3). Nevertheless, they yield comparable performance gains when assessing agents' improvement (ef. Figures 12 and 11).
27

---

PAC Learning with Improvements
LWBCE WPN 1.0)
T.BCE(WEEN = 2)
Caaco, (Wyr 3.0)
Feece: (Ah 6.0)
Escz
Ceace. (Wi 3.0) - Evece: (wer - 6.0)
(1pp-110 1.00
4.0)
(Myp
Lupee: (Wip 2.01
Caaco. 1Wy 5.0)
Fadcs 8.0)
Cacce (Wip 2.0)
Cadce. (Wip 5.0)
Luece: Ewop 8.0)
0.25
Monel (0)) Emor
0.20
Model (h) Eror
Adult
0.15
0.10
0.10
0.05
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
0.0
0.5
1.0
2.5
2.0
2.5
3.0
3.5
4.5
improvement Budg
Improvement Budget in
(a) Adult (CuBCE(WEN = 1.0))
(b) Adult (COBCe CROBCE(WWeN 0.001))
Loce
1.k Caats. IMye 3.01 - Ewere (Mey = 6.0)
Eacz
Cwaces (Myp 3.0) - Cuere (Wey = 6.0)
(Wyy 1.00
4.0)
7.0)
HWpp 1.0)
4.50
Euoce 7.0)
Lueee (Why 2,0)
<aace 1Mar 5.0)
Aveer 8.0)
Later. 1Wim 2.00
Leace, (Mip 5.0)
Luece (Why 8.0)
0.65
0.60
OULAD
Madel Emmer
0.50
0.45
0.4
0.35
0.30
0.25
0.0
0.5
1.0
3.0
6.0
0.0
0.5
1.0
3.0
4.0
Improvement Budg
Improvement Budget ir)
(c) OULAD (CwBce(wex= = 1.0))
(d) OULAD (WUNCE(WEN 1.33))
1Mh 3.00
Custos [Wa 6.0)
Cars Cuarz.
Cwacs, (Mlpp- 3.01
Canca LWo - 6.0)
1.0)
4.01
Cantra (Wpa 2.0)
Cunco 18pp 5.00
Cunce 1Ma 8.0
Cuarr.
Cwars. (Mlye
Cuare.
0.225
0.8
Law school
0.200
0.7
Monel (0) Emer
0:175
0.150
0.5
0.325
0.100
0.075
0.2
0.000
0.1
0.025
0.0
0.0
2.5 Improveeeent Budget (r)
3.0
0.0
0.5
1.5
255
3.0
3.5
Improvemment Budget (1)
(e) Law school (CwDCT (WTN = 1.0))
(f) Law school (LwBCE Cooace((upp (WPN 0.009)
[Map 3.0)
[Wer 6.0)
Cacs
(Wip 3.0)
Cuecp: (wop 6.0)
19h
Contos
1Mar 1.0)
Casco (Mpp = 2.0)
Caaco 110pp 5.00
Cunce (1yg 8.0
Casca 18hp 2.0
Caacs (Mi 5.0)
Kusca. (mp 8.0)
0.625
Synthetic
Model (0) Frrr
0.020
Modal (h) Error
0.15
0.015
0.010
0.10
0.005
0.05
0.000
0.00
0.5
0.5
1.0
2.0
2.5
3.0
3.5
0.0
0.5
1.0
2.5
2.0
2.5
3.0
4.0
Improvement Budget (1)
Improvement Budgett (r)
(g) Synthetic (AwBCE (Wyx 1.0))
(h) Synthetic (LARCF (WFN 0.009)
Figure 8. Comparison the error drop rate when agents improve to the risk-averse models trained with LWRCF where wax = 1.0 ((a). (c). (c), and (g)) and where wex ((b), (d), (f), and (h)) is optimized and false positive weight is varied wPp {1)s across different datasets (Adult, OULAD, Law school and Synthetic). The standard model (black line) trained with Lace loss function is such that whp = wpx = 1, and in all cases an agent is classified as positive if the probability of being positive is above 0.5.
28

---

PAC Learning with Improvements
TN
PNooFP (BC()
TN40FF (aBCZ)
PN468
TP
PN
TN
10
Percentage (%)
Percentager (%)
8D
10
40
10
20
1.0
0.0
1.5
2.5
3.0
4.0
Budget
Budget
(a) Adult (Movement of agents from TN/EN to TP/FP)
(b) Adult (FNR/FPR before and after agents' improvement)
TN4o-PP (BGE)
PN46FFP
Th-4FFP (nBIC)
PloosFPP (eCCE)
(BCE)
(BCE) (BCE)
(+BCE) (fer(
FN
(NECE
FNR (BC:)
(MOCE)
100
Percentage (%)
60
Percentages (%)
40
20
20
0.0
0.5
1.0
1.5
2.0 Budget
2.5
3.0
3.5
4.0
2.0 Budget
(c) OULAD (Movement of agents from TN/EN to TP/P)
(d) OULAD (FNR/FPR before and after agents' improvement)
(BCE) alter (BCE)
(BCE) (9CE)
before (AECE) (+BCE)
(NBCE)
(9GE)
(BCE)
after (wBCE)
10
Percentage (%)
Percentages (%)
15
10
10
5
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
Budget
Budget
(e) Synthetic (Movement of agents from TN/FN to TP/FP)
(f) Synthetic (ENR/FPR before and after agents' improvement)
Figure ((a), (c), and (e)) The percentage negatively classified agents (TN FN) that transition to and after responding to the classifier (f(r)). ((b). (d), and (f) The FPR and FNR before and after agents move. On the adult dataset, the wBCE-trained model used Whp = 0.001 and Wyn = 4.4, while on the OULAD dataset, it used wap 1.33 and wsn 2, and on the synthetic datasct, Wyr = 0.009 and = 1.0. In all cases, BCE- trained models used Wpr wex 1, and in all cases agent is classified as positive if the probability of being positive above 0.5.
29

---

PAC Learning with Improvements
Threshold = 0.5
Threshold = 0.9
Eseris (19sa 3.0)
feacs, (Mh - 6.0)
Castas (M 3.0)
Eaaca (Wiaa - 6.0)
Cusco (Mtpp 1.0;
Lieez: (My
Lears (My
Eaacs (My 1.0)
Caaco (My
Lxnce (M1
Cancs (Wr 2.0)
Fweras (1ra 5.0)
Cwacs (Wk, - 8.0)
Caacs (Wy 2.0)
Cwacs UW 5.0)
Fwaress (Mra 8.0)
Model (h) Error
Model (n) Error
0.20
Adult
0.15
0.15
0.10
0.10
0.05
0.05
0.00
0.00
1.0
2.0
2.5
3.5
1.0
2.0
2.5
3.0
3.5
4.5
Inprovementt Budget (1)
Improvement Budget (1)
(a) Adult (CowBE (wpp = 0.001))
(b) Adult (LwBCE(WTX = 0.001))
Eycs
feecci (191 m 3.0) Leacz (Myp i 6.01
Eact
Eyaco (Myp m 3.0) Gucce (Wyp = 6.0)
Canta (1ta 1.0)
Faercs (1his 4.00
Caacs EMi - 7.0)
Fasts: [M6p 1.0)
(Wh 4.0)
Ewara (Misa - 7.0)
Cuece 2,0)
Cueces (tter
Saarz (Wy
Caace, (Wer 2.0)
Cancos 5.0)
Cwece (Iry 8.0)
0.65
OULAD
0.55
0.60
0.50
0.50
Model
0.40
0.45
0.35
0.35
0.25
0.30
0.0
0.5
1.0
1.5
2.0
25
3.0
3.5
6.0
0.0
0.5
1.0
2.0
25
5.0
3.5
4.0
Improvement Budget (n
Improvement Budget (n
(c) OULAD (Cuncr (WFY 1.33))
(d) OULAD (CuRCr (WFN 1.33))
Cacs
Cuncss
Cuacss (Whss
Custss 3.0)
Cuacs,
(Wip = 1.0/
Cupcs, (Wyp - 4.0)
Lupcs (Wyp 7. (.0)
Gxtce (Wap - 1.0)
Cxtce (Wip 4.0) ... Coace, [Wip - 7.0)
(W = 2.0)
EMes 5.0)
(Was - B.0)
Cuarss (Wiz 2.0)
Cuacss (Mii 5.0)
(Wap - 8.0)
0.8
Law school
(m) Eror
0.7
Model (P)) Error
0.6
0.5
0.6
0.4
0.4
0.2
0.0
0.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
Improvement: Budget 01
Improvement Budget (n
(e) Law school (LwBCE (WTN 0.009))
(f) Law school (CABCE (WTN 0.009))
Luece,
Cxdce 3.0)
Exece
Cuncia (1ti - 1.0)
Contaa (Wis 4.0)
Casca (Wh, 7.0)
Caacs. [Wsp= 1.0)
Cuazis DW1 4.0)
Gwaca (W9. 7.0)
Cuece (Mip 2,00
fucce: (mer 5.0)
Cuacs (Myy = 8.0)
Eyecs (Wy 2.0)
Cuaco (Whp 5.0)
Cxece (Myp = 8.0)
Synthetic
(1) Error
Model (0) Error
0.25
0.15
0.20
0.10
0:30
0.05
0.05
0.00
0.00
1.0
3.5
2.5 Improvement Budget (M)
4.0
Budget
(g) Synthetic (CuBCF(ws) = 0.009))
(h) Synthetic (CuRch = 0.009))
Figure 10. Comparison of the error drop rate when agents improve to the risk-averse (LWBCF, wPN (Cacn, wip wyx = 1) models across four datasets (Adult, OULAD, Law school, and Synthetic). Column one ((a), (c). (e) and (g) considers models where an agent is classified as positive if the probability of being positive is above 0.5 and column two ((b), (d), (f) and
"0 1, Wsp = {+)=_1) and standard
(h)) considers models where a higher threshold used 0.9. Increasing the improvement budget and classifier risk aversinn (high wep leads to a sharper error drop rate, and loss- based risk aversion is more effective than the threshold based risk-aversion.
"ije )
30

---

PAC Learning with Improvements
Lsce
... Lasce (Wye - 3.0) --- Laace. (Wyp - 6.0)
Eacz
... Lunce, =300 --- Cance (Wrp = 6.07
Crece, (Wis= 1.0)
Lasce (Wip 4.0)
Cwece: (Wyp 7.0)
Cwace, (Wer
Luacr, (Wop
Laacz, (Wrp
(Wip 2.0)
Cancer
2.0)
5.0)
Concr.
0.65
0.60
Model (b) Error
0.50
(b)
0.45
0.40
0.3
0.35
0.30
0.2
0.25
Improvement Budget (r)
Improvement Budget (n)
(a) OULAD (DTC1)
(b) OULAD (RFCI)
Lece
Evoce: (Way
Gusce: (Wip
Lecs
Lwece: (Wip 3.0)
Cascs (Wip
Cunce,
Goace,
Cwace,
(Wip
Coace,
Ovecs: (Wrp 2.0)
Cwocs: (W 5.0)
Cuecs. (Wip 8.0)
Evecs. (Wrp 2.0)
Cwscs: (Wip. 5.0)
Ceece: (Wsp B.0)
0.6
0.6
Model (h) Error
0.5
Model (h) Error
0.4
0.2
0.2
0.1
Improvement Budget (r)
Improvement Budget (r)
(c) OULAD (RFC2)
(d) OULAD (XGB)
Figure 11. Risk-averse (CwBce with Wep [i] = 1.33) and standard (CaCE, WPN trained model function (h) error drop rates versus improvement budget (r) on the Adult dataset where different singularly-defined f are used to verify successful-ness improvement: ((a)) with fi ((b)) with fš. ((c) with fi, and ((d) with fö. For DTC2, fī see Figure 10c. In all cases, the threshold for classifying an agent as positive is 0.5.
31

---

PAC Learning with Improvements
3.0)
3.0)
Cancr, (Wrp = 1.0)
- Lunce (Wrp = 4.0)
--. Laacr, (Wrp = 7.0)
Exace, (Wrr = 1.0)
- Cance. (Wro = 4.0)
--- Ewaer. (Wrp 7.0)
Cxoce, (Wsp 2.0)
Lasce: (Wy 5.0)
Enace: (Wyr 8.0)
Cyoce (Wap 2.0)
Casce: (Wyr 5.0)
Ewecz: (Wy 8.0)
0.20
Model Error
0.55
0.15
0.50
0.10
0.40
0.05
0.35
0.00
0.0
0.5
1.0
1.5
2.0
3.0
3.5
4.0
0.0
0.5
1.0
2.0 Improvement Budget (n)
3.0
3.5
4,0
Improvement Budget (r)
(a) Adult (WYN = 0.001)
(b) OULAD (WEN = 1.33)
Lace
Cuace, (Wrp - 3.0) Guace (Wip 6.0)
(Wer 3.0)
6.0)
Evece: (Wr 1.0)
Cwocs, (Wrp 4.0) ... Guece: (Wi 7.0)
Eyecz, (Wrp 1.0) - Cance: (Wrp 4.0)
--- Ewecz (Wrp 7.0)
Cuarz, (Wrp 2.0)
Cuacr, (Wrp Caarr (Wrp
Cyece- (Wap 2.0)
Casce: (W, 5.0)
Ewece: (Wy
Model (b) Error
0.20
0.15
0.44
0.10
0.3
0.05
0.1
0.0
0.00
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
0.5
1.0
2.0
3.0
3.5
Improvement Budget (r)
Improvement Budget (7)
(c) Law school (WyN = 0.009)
(d) Synthetic (wex = 0.009)
Figure 12. Risk-averse (CwBce with wyp (1) and standard (CuCE) trained model function (/) error versus improvement budget (r) across four datasets (Adult, OULAD, Law school, and Synthetic). For all cases, the threshold for classifying agent positive 0.5 and multi-defined f model is used to verify successful-ness of improvement. Increasing the improvement hudget and classifier risk-aversion (high 2mz leads faster error drop rate.
wgx
32


Reviews:
[{"review_id": "sZQnVsNcjp", "reviewer": "Reviewer_Hznw", "summary": "The paper proposes a variant of PAC learning where the data points are conceived as agents that can move around by a small amount and thus if they are close to the decision boundary, they can be classified as desired (typically positive; e.g., for receiving a loan after some small \"effort\" in order to move their precise coordinates).  The authors formulate this approach and consider sample complexity results; e.g., situations where learning is easier or situations where learning is harder.  While the authors provide several theoretical results, they also provide experimental evidence in the end in order to show the effectiveness of the proposed method in real-world datasets.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to review our work. Below are responses to the questions they raised. \n\n\n>Terminology - “hypothesis class”[H]  vs. “concept class” [C]\n\nWe indeed make the common assumption of implicitly taking H=C.\nWhile 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. \nSee, 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).\n\n[1] Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.\n\n[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.\n\n[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.\n\nTo 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. \n\n\n>“hypotheses\" outside of the \"hypothesis class\" (page 2, footnote 1)”\n\nActually, 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”.\n\n>“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!!”\n\nWe 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:\n“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). \nWe believe this terminology is easier to understand, but we emphasize that the statement is already correct as it is, without any further changes.\n\nWe would be happy to answer and clarify any further questions.", "claims_and_evidence": "For the largest part the paper has clear and convincing evidence.  \n\nHowever, the authors have some issues with traditional terminology.  In particular the authors mix the notions of \"concept class\" and \"hypothesis class/space\" (e.g., line 78 right column; they treat them as if they are the same, when they are not).  Based on what I read in the paper, I believe that the authors fail to realize that the term \"hypothesis\" corresponds to the function that is being learnt from data and is the output of a learning algorithm.  The name is fitting because it is really a \"guess\" for the ground truth function, which we typically call \"concept\".  The reason that we call a function a concept probably has its roots in the early days of learning theory where functions were (and still are) seen as languages over an instance space that describe a particular concept of interest (that we want to learn).  \n\nIn other words, the ground truth is a concept (function) from the concept class and a hypothesis is a function that we learn and it is one of the permissible functions from the hypothesis space (or, hypothesis class).  Due to this misunderstanding, the authors even propose the existence of \"hypotheses\" outside of the \"hypothesis class\" (page 2, footnote 1), which is completely preposterous.  Along these lines the authors mix things again (line 120, right column) where they want to make a connection between learnability and the VC-dimension.  While such a connection exists, the connection really refers to the VC-dimension of the hypothesis space; the space of functions that the learner considers and may produce in the output; not on the space of functions from where the ground truth is potentially coming from and is the claim of the authors.\n\nIn line 190 we read about a \"non-realizable target concept f^*\" that is not part of the hypothesis space.  While in general this would not be a problematic statement, if we think a little bit about the definitions that the authors have provided in the paper, 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!!  What is the hypothesis class then?  Again, in order to help the authors: the hypothesis class is the set of functions among which the learner has to choose one and output as a result of the learning process given a particular dataset.\n\nIn general, I think the authors have a good story to tell and some very interesting results.  However, some of the claims are outright confusing because of all the above.  For this reason, I believe a revised version of the paper will be much more interesting for everyone and this is why my current recommendation will not be for accepting this paper.", "methods_and_evaluation_criteria": "Yes, they are ok.", "theoretical_claims": "Yes, I checked several proofs.  However, there are several leaps of faith due to the non-standard and inconsistent use of terminology for machine learning theory.", "experimental_designs_or_analyses": "The experiments look ok.", "relation_to_broader_scientific_literature": "Again, I need to stress the fact that the authors use traditional terminology in a very non-standard way.  While I really like the ideas of the paper and the results that the authors have, nevertheless, these need to be stated in the appropriate/standard context for machine learning theory.  Unfortunately, this is not where the paper is standing right now.", "essential_references_not_discussed": "I think everything is fine w.r.t. the references.", "other_strengths_and_weaknesses": "I think this paper has very interesting ideas.  However, these need to be presented in the appropriate context.  And this is especially true because ultimately the authors want to provide results that separate their model from traditional model of learning.  But if their description for traditional model of learning has many holes, then, unfortunately, the paper is not ready yet.  Again, I like the paper a lot, but a revision is needed before it gets published.  This way all the results will make more sense and can be seen under the appropriate context.", "other_comments_or_suggestions": "There were a couple of typos here and there, but they were really minor.", "questions_for_authors": "Q1.  If you think your understanding of the hypothesis space and concept class are appropriate as you have defined things in the paper, please argue a bit more here and we will find the \"truth\" together.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JbNX3LuX77", "reviewer": "Reviewer_j13z", "summary": "This paper introduces a novel framework called PAC learning with improvements. The manuscript outlines the setting as one in which data points correspond to individuals that can improvement themselves. A key feature of this framework is that the improvement is real and as such, a classifier can be correct on a point that would have been misclassified before the improvement is made. For each data point there exists a set of improvement points each individual can transition to after observing the classifier h. In this setting, the paper provides the following results: A separation from classical PAC learning, proof of learnability of classes that are closed under intersection and finally learnability under a graph-model. Finally, the paper provides an empirical study of the ideas developed in the manuscript.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for appreciating our work, and for the insightful questions and suggestions.\n\n>Relationship between FP weight and imbalance \n\nAt 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.\n\n>Intuition on behavior when $w_{FP}$ is increased and why the error consistently larger \n\nIncreasing 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. \n\n>``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?''\n\nAgents 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.\n\n> Connection of the experiments to the theoretical results. \n\nThank 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:\n\"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).”\n\n>.., it might be useful to relate this more clearly to existing work such as strategic classification.\n\nThank 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.\n\nConcretely, 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).\n\nWe will add the above examples that establish a separation between our model and strategic classification to clarify the comparison with the strategic classification model.", "claims_and_evidence": "The first claimed contribution of the paper is a novel framework for PAC learning under improvement which is given in section 2.\nThe second claim is that there is a separation between PAC learning and PAC learning with improvement which is provided in Theorem 3.1.\nThe third claim is that intersection-closed classes are learnable. Evidence is provided in Theorem 4.7.\nThe learnability of the graph-based model is proven in Theorem 5.2.\nFinally, in the experimental section it is claimed that among risk-averse strategies, loss-based risk aversion proves most useful in the learning with improvement setting. Furthermore, it is shown that only small budgets of improvement are sufficient to increase performance and that the dataset characteristics influence the required level of risk aversion. Support for these claims is provided in Figure 2.\n\nAll Theorems are appropriate for the respective claims and the experimental section’s conclusions are accurate but broadly stated. I think it would be good to explicitly tie the language to the selected datasets since generalizing claims about parameters are difficult. The sentence in line 436L makes it sound like the findings are general but in line 410R the text specifically talks about diminishing gains under a specific r. The r under which benefits diminish is highly data dependent as we can see in the Appendix. One could point out that in all cases, after r reaches a certain threshold, performance gains diminish.", "methods_and_evaluation_criteria": "The experimental section 6 uses three tabular datasets as well as one synthetic 8-dimensional dataset. A true labeling function is obtained via a zero-error model trained on each dataset. The datasets all represent social situations in which humans are the data points and in theory these points could improve. This seems like a sensible choice for an evaluation. Given that the claims are about 0 model-error, evaluating model error is also the correct metric. Plotting error against budget is a sensible choice.\nOverall, the experiments provide some nice intuition about the risk-averseness of a model and learning with improvement.", "theoretical_claims": "I was able to follow all proofs in the paper and did not find anything immediately wrong with them. I did not carefully check additional proofs in the appendix. However, the results in section 4 seem quite intuitive.", "experimental_designs_or_analyses": "I did verify the experimental design. One thing that I am missing in the text is a direct relation between the theoretical results that were demonstrated and the empirical design. This is mostly an issue of exposition I believe. But I do think that several interesting question arise from this connection, see, e.g. Q4.\n\nAnother  thing that is missing is a measure of variance. It is not immediately clear if the results are statistically significant. However, given that the results are consistent across multiple datasets, it is likely that the interpretation of these results is valid.\n\nThe experimental design is interesting as it outlines a general approach to improvement but the improvement function is difficult to interpret. I think adding more intuition as to how the improvement functions impact these results would have been nice. One thing that is now clear is at which point classification becomes trivial, i.e. when does an all 1 classifier get 0 error. I think it would be good to address this in the main text. See Q3 below.", "relation_to_broader_scientific_literature": "Overall, I think this discussion is decent. However, especially in cases where frameworks are very similar to each other, I believe it is useful to have a clear formal description of how the proposed framework differs. In this case, it might be useful to relate this more clearly to existing work such as strategic classification.", "essential_references_not_discussed": "I’m not sufficiently familiar with the literature to make a statement here.", "other_strengths_and_weaknesses": "The paper is very well written and has a clear structure. The manuscript does a good job of providing intuition with examples before stating full proofs which makes it easy to read and makes it easy to extract the key properties of the proposed framework.", "other_comments_or_suggestions": "It may be worthwhile to consider making the title a little more explicit. When I first saw the title, I thought the paper was going to provide improved PAC bounds, not that there would be a new PAC framework.", "questions_for_authors": "Q1. In the experiments, what is the relationship between false positive weight and imbalance in the corresponding datasets?\n\nQ2. Can you provide an intuition for behavior when $w_{FP}$ is increased? Why is the error consistently larger across all datasets?\n\nQ3: 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?\n\nQ4 We know that neural networks learn low-dimensional representations, often explainable in 2 dimensions in which data points become separable. Are you aware of any work relating the intersection-closed property to encoders/embeddings of trained neural networks?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PfuERtKFEb", "reviewer": "Reviewer_X3yH", "summary": "This paper continues the line of work on strategic classification and related settings. The authors consider a binary PAC learning setting where negatively predicted points $x$ can change their prediction slightly (defined by some set $\\Delta(x)$); the expected loss is then evaluated on this potentially altered predictions. Various results are proven: \n1. Learnability is here not captured by the VC dimension.\n2. state a distinction for the case when the target $f\\notin\\mathcal{H}$\n3. learning halfspaces (with the natural definition of $\\Delta$)\n4. learning intersection-closed spaces $\\mathcal{H}$ with arbitrary $\\Delta$ relying on the Closure algorithm\n5. learning with finite domains where $\\Delta$ is given by a graph. Here they achieve near-tight sample complexity bounds to get $0$ loss, which is not possible in standard PAC.\n\nFinally some experiments on smaller datasets are provided (UCI etc.)\n\n## update after rebuttal\n\nChanged score to 5 to emphasize the overall quality of this work and the fact that the reviewers clearly addressed mine and others' concerns.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive comments and very interesting questions which inspire directions for promising future research.\n\n>“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?”\n\nThank 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). \n\n> “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?”\n\nThe 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.\n\n> Not important comment: Note that what you call \"non-realizable\"...\n\nWe 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:\n“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).”\n\n> On the different problems considered and the overarching picture\n\nAs 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^*$).\n\nWe 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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I checked the proofs, they are correct.", "experimental_designs_or_analyses": "Solid experimental evaluation with simple UCI datasets and related.", "relation_to_broader_scientific_literature": "Solid discussion of related work. Perhaps mention that the graph-case you consider is very related to the manipulation graph in previous papers (Cohen et al., Lechner&Urner, ...).", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Interesting results continuing an important line of work. Clearly fits ICML and is very well written. I vote for acceptance.\n\nOne small weakness: The different considered problems (halfspaces, intersection-closed, graph-case) are somewhat scattered and disconnected; there seems to be no clear overarching general picture or theory (which, however, makes sense as for general $\\Delta$ the situation is rather complex).", "other_comments_or_suggestions": "Not important comment: Note that what you call \"non-realizable\" (the fact that $f^*\\notin \\mathcal{H}$) but still assume there is an $h$ that has 0 true loss, is typically still referred to as \"realizable\" in the literature (see e.g., Def 2.1 in the \"Understanding Machine Learning\" book (2014)).", "questions_for_authors": "1. The threshold/halfspace examples have vague similarities with learning with margin (or perhaps a one-sided version of it). Is there any relationship of the setting here and learning margin halfspaces or partial concept classes in general?\n2. Is there some natural (sufficient) requirement on $\\Delta$ (and/or $H$ and the used learning algorithm as in Thm 4.7) such that finite VC is sufficient for learning here? Perhaps some sort of monotonicity or smoothness?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "h4KfAdZJwW", "reviewer": "Reviewer_miAH", "summary": "The paper studies a scenario in which \"agents\" adapt in response to the classifier deployed by the learner. Within the PAC framework, the authors derive an upper bound for certain standard hypothesis classes.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">“why should the hypothesis be penalized at point despite being correct there and offering at least 1 valid improvement option?”\n\nThank you for your question.   \nLet'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. \n\nAnother 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.”\n\nFurthermore, 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. \n\n>“.., is the closure algorithm always a valid PAC learner, although it becomes improper when the hypothesis class is not intersection-closed?”\n\nThis 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. \n\n>“A more thorough comparison with the adversarial robustness literature.”\n\nThank 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:\n- 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.\nThis 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).\n- 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.\n- 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.\n\nIn 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]. \\\nOur 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.\n\nWe will add the above discussion in our revision. We are happy to answer and clarify any further questions.", "claims_and_evidence": "Yes, all the theoretical claims are justified by either proof or a sketch of it.", "methods_and_evaluation_criteria": "Experiments were conducted on three real-world datasets: Adult UCI, OULAD, and Law School. While these datasets do not precisely reflect a scenario in which agents actively improve based on the deployed model, they broadly capture the underlying concept, serving as a proof of concept.", "theoretical_claims": "I verified the details of the examples and proofs included in the paper's main text.", "experimental_designs_or_analyses": "The experimental setup looks good.", "relation_to_broader_scientific_literature": "This problem is closely related to research in fairness and performative prediction. Additionally, the loss function formulation suggests a connection to the literature on adversarial robustness.", "essential_references_not_discussed": "The authors should provide a more thorough comparison with the adversarial robustness literature. In adversarial robustness, the robustness set is predefined and independent of the deployed hypothesis, whereas in this setting, it depends on the hypothesis itself. While these two problems are not always equivalent, their equivalence depends on how the robustness set is defined. A well-known result by [MHS2019] shows that the VC dimension is generally insufficient for proper learnability but sufficient for improper learnability. Given the similar findings in this paper, there may be a deeper connection worth exploring.\n\nTo that note, is the closure algorithm always a valid PAC learner, although it becomes improper when the hypothesis class is not intersection-closed? If so, this would lead to a conclusion similar to [MHS2019] in the context of this paper: PAC learning with improvements is possible for all VC classes, but only in an improper manner.\n\n1. Montasser, Omar, Steve Hanneke, and Nathan Srebro. \"Vc classes are adversarially robustly learnable, but only improperly.\" Conference on Learning Theory. PMLR, 2019.", "other_strengths_and_weaknesses": "The problem is interesting and well-motivated in the context of modern AI development.  \n\nHowever, it is unclear whether the loss function accurately represents the intended setting. See the questions below for further clarification.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "I am unsure whether the loss function accurately reflects the scenario the authors aim to capture. Given a deployed hypothesis $h$, the loss function is defined as  \n\n$$\n\\ell(x, h, f^{\\star}) =\\max_{z \\in \\Delta_h(x)} \\mathbb{I}[h(z) \\neq f^{\\star}(z)].\n$$\n\nConsider a case where $h(x) = 0 = f^{\\star}(x)$, and the improvement set is $\\Delta_h(x) = \\{z_1, z_2\\}$, with $h(z_1) = h(z_2) = 1$. Suppose $f^{\\star}(z_1) = 1$ but $f^{\\star}(z_2) = 0$.  \n\nHere, the hypothesis $h$ correctly classifies the base point $x$, and there exists at least one point in the improvement set, $z_1$, where the agent can move and still be classified correctly. However, the loss is  \n\n$$\n\\ell(x, h, f^{\\star}) = \\max \\(\\mathbb{I}[h(z_1) \\neq f^{\\star}(z_1)], \\mathbb{I}[h(z_2) \\neq f^{\\star}(z_2)]  \\) = \\max \\( 0, 1\\)= 1.\n$$\n\nSo, my question is: why should the hypothesis $ h $ be penalized at point $ x $ despite being correct there and offering at least one valid improvement option? This appears to be a significant weakness in the formalization of the problem.  \n\nThat said, I may be misunderstanding the intended reasoning, and I am open to engaging with the authors during the rebuttal process to clarify this issue. If a justification is provided, I am willing to reconsider my assessment. However, in its current form, I cannot recommend acceptance.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper deals with a learning-theoretic scenario where points (e.g., agents) can "improve" their features. While a similar setting was studied extensively in the "strategic classification" literature, this paper poses a novel challenge: Under such improvements, can we learn what is unlearnable in the standard PAC framework?

The reviewing committee had several disagreements, and all discussions (rebuttal, author-reviewer, reviewer-reviewer, and AC-reviewer) were extensive and engaging. All reviewers appreciate the results of this paper and believe it is both novel and contains non-trivial contributions that deserve to be published in a top ML conference.

The main concern raised by the reviewers was the use of imprecise or misleading terminology in several parts of the paper, primarily around the distinctions between proper vs. improper learning and agnostic vs. realizable settings. This lack of clarity makes certain arguments and claims in the paper difficult to interpret. The authors acknowledged this issue in their rebuttal and committed to addressing it upon acceptance. In addition, they provided, as part of their rebuttal, a detailed breakdown of the key theoretical statements and clarified how each aligns with the appropriate definitions.

After all discussions, during which one reviewer increased their score and suggested championing the paper, another reviewer suggested that the required modifications may be non-trivial and warrant a new revision of the paper.

To make my final decision, I have read the paper and all the associated reviews and discussions carefully. I recognize both the merits of the paper and the critical perspective. Ultimately, I see this as a question of risk assessment. In my view, the necessary revisions are minor and well within the scope of a camera-ready version, and I trust the authors' clear commitment to address them. I acknowledge that this judgment could prove optimistic; for example, some statements may turn out to be ill-defined and require further clarification. However, I believe that delaying publication on these grounds would be unfair to the authors, most of the reviewers, and the community. I therefore vote for accepting this paper.
Decision: Accept (poster)