Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning
Authors: Dravyansh Sharma
Alec Sun
Venue: NeurIPS 2025 spotlight ()
Keywords: PAC learning
online learning
sample complexity
learning with agents
Primary area: theory

Abstract: Machine learning is now ubiquitous in societal decision-making, for example in evaluating job candidates or loan applications, and it is increasingly important to take into account how classified agents will react to the learning algorithms. The majority of recent literature on strategic classification has focused on reducing and countering deceptive behaviors by the classified agents, but recent work of Attias et al. identifies surprising properties of learnability when the agents genuinely improve in order to attain the desirable classification, such as smaller generalization error than standard PAC-learning. In this paper we characterize so-called learnability with improvements across multiple new axes. We introduce an asymmetric variant of minimally consistent concept classes and use it to provide an exact characterization of proper learning with improvements in the realizable setting. While prior work studies learnability only under general, arbitrary agent improvement regions, we give positive results for more natural Euclidean ball improvement sets. In particular, we characterize improper learning under a generative assumption on the data distribution. We further show how to learn in more challenging settings, achieving lower generalization error under well-studied bounded noise models and obtaining mistake bounds in realizable and agnostic online learning. We resolve open questions posed by Attias et al. for both proper and improper learning.

Conservative classifiers do consistently well with improving agents: characterizing statistical and online learning
Dravyansh Sharma
Alec Sun University of Chicago
Northwestern University Toyota Technological Institute at Chicago
Abstract
Machine learning is now ubiquitous in societal decision-making, for example in evaluating job candidates or loan applications, and it is increasingly important to take into account how classified agents will react to the learning algorithms. The majority of recent literature on strategic classification has focused on reduc- ing and countering deceptive behaviors by the classified agents, but recent work of Attias al. [5] identifies surprising properties of learnability when the agents genuinely improve in order to attain the desirable classification, such as smaller generalization error than standard PAC-learning. this paper we characterize so-called learnability with improvements across multiple new axes. We introduce an asymmetric variant minimally consistent concept classes and use to pro- vide an exact characterization of proper learning with improvements in the real- izable setting. While prior work studies learnability only under general, arbitrary agent improvement regions, give positive results for more natural Euclidean ball improvement sets. In particular, we characterize improper learning under a generative assumption the data distribution. We further show how learn in more challenging settings, achieving lower generalization error under well-studied bounded noise models and obtaining mistake bounds in realizable and agnostic on- line learning. We resolve open questions posed by Attias et al. [5] for both proper and improper learning.
Introduction
Suppose that a school is trying create machine learning classifier admit students based on their test score. The school uses a cutoff determine whether a student should be admitted. If the school publishes this cutoff, then students immediately below the cutoff will want to boost their test scores order be admitted, for example by studying harder or by registering for booster courses. This is an example of where deploying classifier can influence the behavior of the agents it is aiming classify. We assume binary classification and that agents want be positively classified.
There are two views one can take on this phenomenon. The first is that the actions that agents take in response to the deployed classifier do not truly improve the agent's 's quality. This setting is known as strategic classification [36] or measure management [16]. A second view, however, which is the focus of this work. is that agents' actions lead real improvements. For example. studying or taking classes in order to get higher exam score can genuinely make a student more qualified, so the school would want to admit any student that achieves their desired cutoff Ó. This setting, when agents respond to the classifier potentially improve their elassification while changing their true features in the process, is known strategic improvements [40, 45).
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Previous works seek to efficiently incentivize and maximize agent improvement [45, 40, 53]. In recent paper, Attias et al. [5] instead take the agent improvement function as given and study statisti- cal learnability with improvements. Attias et al. [5] show fundamental differences in the learnability of concept classes compared to both standard PAC-learning where the agents cannot respond to the classifier, as well as the strategic setting where the agent tries to deceive the classifier to obtain a more favorable classification. Surprisingly, learning with improvements can sometimes be casier than the standard PAC setting, and it can sometimes be harder than strategic classification. Attias et al. [5] provide concrete examples showing the separation between standard PAC-learning, strate- gic PAC-learning, and PAC-Iearning with improvements. Attias et al. [5]'s results focus realizable and fully offline learning. They give necessary and sufficient conditions for proper learning in terms of the intersection-clssee property of concept classes.
In this paper, we give an exact characterization of which concepts classes are PAC learnable in the proper and realizable setting using new notion which we call nearly minimally consistent concept classes. This improves upon prior work by closing the gap between the necessary and sufficient conditions for proper, realizable PAC learning. We also design classifiers to maximize accuracy for strategic improvements in more challenging settings as well as under more natural assumptions. For improper learning, we show natural sufficient condition the data distribution for learning when the agents can improve within Euclidean balls. Under this condition, we obtain tight sample complexity bounds, up to logarithmic factors.
Next, we turn our attention to learning with improvements in more challenging settings. We study learning with bounded label noise (including random classification noise and Massart noise), where we can no longer rely on positive labels in our training set as being perfectly safe. For example, a weak student who studied a small random subset of the syllabus might get lucky with some small probability if the test questions happen to be from the part the student reviewed. We show how to de- sign Bayes optimal classifiers, that is achieve OPT expected error in the learning with improvements setting. In contrast, one can only hope to achieve OPT + E in standard PAC learning.
Finally, we initiate the study of online learning with improvements, which may be more realistic than assuming that the agents come from fixed distribution. This particularly important to study when agents can move in response to our classification over time. For example, a false positive in our published classifier may be exploited by an increasing number of agents. Further, we handle even the agnostic learning in the online setting where no classifier available to the learner may be perfect. We design "conservative" versions of the majority vote classifier which achieve near-optimal mistake bounds for both realizable and agnostic online learning with improvements.
Contributions. Our paper makes the following contributions learning with improvements in challenging and natural settings:
Proper learning for any improvement function. In Section 3, we introduce a new property of concept classes called nearly minimally consistent and show that this property fully characterizes which concept classes be learned with improvements for any improvement function in the proper, realizable setting. This resolves an open question of Attias et al. [5].
Improper learning for Euclidean ball improvement sets. In Section 4, we move beyond proper learning. We show that to get positive results in the improper setting we need to make assump- tions about both the agent improvement set and the data distribution. We prove that the simple memorization learning rule can learn any concept class improperly, even those with infinite VC- dimension, assuming that the improvement set or contains a Euclidean ball and that the data distribution satisfies a coverability condition. Both of these assumptions are natural and appear in prior literature. This addresses another question raised by Attias et al. [5].
Learning with noise. Section 5, we construct optimal algorithms for learning linear separators in the improvements setting with bounded label noise under isotropic logconcave distributions and instantiate our algorithms for many well-studied noise models. To the best of our knowledge, we are the first to consider learning with strategic agents under label noise.
Online learning on a graph. In Section 6, we study mistake bounds for online learning with improvements for the discrete graph model of Attias et al. [5] in the more challenging online setting. In both realizable and agnostic settings, we prove that risk-averse modifications of the weighted majority vote algorithm enjoy near-optimal mistake bounds.
2

---

Related work. In each of the settings we study above, we discuss the conceptual differences be- tween learning with improvements and learning under strategic classification. More generally, our paper is related to several works studying learning in strategic and adversarial environments, such as strategic classification [37, 46, 19, 1, 35], learning with improvements [40, 35, 5], reliable learning [49, 33], and learning with noise [10]. For detailed discussion of related work, see Appendix A.
2
Model
Attias et al. [5] propose the following formal model for learning with improvements. Let X' denote the instance space consisting of points or agents, and the label space is binary {0. 1}. Here the label 0 is called the negative class and label is called the positive class, and all the agents would prefer improvement function that maps each point r E X' to its improvement set A (zx), to which x can potentially move after the learner has published the classifier in order to be classified positively. For example, X' S Rdd, natural choice for A A(x) could be an fz-ball centered at x. Let H C {0, 1 denote the concept space, that is, the set of candidate classifiers. We assume the existence of a ground truth function f : X - {0, 13. which represents the true label of every point.
to be classified positive. Let A X - 2 denote
The goal is learn the ground truth by sampling labeled instances from X. After seeing several samples from X. the learner will publish classifier h X' - {0, 1}. Each point now reacts to h in the following way: the agent was classified negative by h, it tries to find a point in its improvement set (xx that is classified positive by h and moves to it. The agent will only move if such a positive point exists. We formalize this as the reaction set with respect to h,
{1o)
(x) (1o E A(x): Mxx)= 13
if (xx) = 1 or if fa' E E 1((2) = 13 = 0 (2.1) otherwise.
An
Note that if h classifies x as positive, stays in place. If h classifies æ negative, there are two cases. Either, there is no point in its improvement set where the agent is classified positive by h and the agent does not move. Else, the agent moves to some point x' to be predicted positive by h. Our improvement set model is equivalent to the behavior of utility-maximizing agents that have a utility equal h(r)) cost(z)), and ((x) = {a' X' cost(2:) < 1}. These agents have utility of 1 for being classified as positive, a utility of O for being classified as negative, and incur cost for moving, where (xx) corresponds the points that can move at cost less than 1.
classification error in the improvements setting said to occur if there exists a point in the reaction set of where h disagrees with f*, namely
Loss(1; h. f*) x' (a)
max
1 (x)) A f (x')
(2.2)
According to Eq. (2.2), agents with h(x) = 0 will improve to point x' in their reaction set with h(z')= = if possible, breaking ties in the worst case in favor of points x' for which f(x') = O. This definition is natural if we want our classifiers to be robust to unknown tiebreaking mechanisms, and would also make sense if improving to points whose true label according to f is negative is less costly than improving to points whose true label is positive. Hence Eq. (2.2) implies that classification error occurs for & if one of the following is true: x itself is a false positive, x is a false negative and there is no positive x' A (x) that can improve to, is negative and there exists false positive x' E Ax that x can move to. This loss function favors conservative classifiers that label uncertain points as negative rather than positive. For example, consider scenario in which { f fz) = 1}. Note that l can have zero loss long as all points x for which h(z)) 0 and f( = can improve some point r E A(z) with h(z')= = 1. Importantly, the fact that some true positives might need to put in effort to improve in order to be classified as positive does not count as classification error in learning with improvements.
there are no false positives, equivalently {x] f(()) = 1} C {a
Remark 2.1. Our improvement set based abstraction has one-to-one correspondence with utility- maximizing agents, including the adversarial tiebreaking behavior, as follows. Set the agent utility to be 1 at positive points x with h(xx) 1, O at negative points a with h((x) = O, and the utility of movement from x to a point x' E A (x) as a real number in [O, 1). As an example, we could set the utility of movement to 1/x A(x)] h((²)- 2a" For this utility function, the agent has no incentive move if either 1|z & A(x)) or h(2²) O, else it has a utility of 2 for ground-truth
3

---

negative points (*(x') O and for ground-truth positive points, so the agent moves in either case but prefers the former. Note that a(x) consists of the points to which the agent x would ever consider (or is able to) move to, and its incentives to move to point within (xx are governed by h(a') and (x²) as described above.
Conversely, our improvement set based abstraction can be used to model an arbitrary function as follows. Without loss of generality say that the utility of being positive is and negative is O. Movements are associated with cost, functions (negative utilities) for each x ~ x' move, and costs outside of (0, 1) can be ignored as the agent either always moves or never moves, irrespective of the classifier. We can define the improvement set (xx) to be the set of points where the cost is in (0. 1). Now the agent with h(x) 0 will move to a point x' with h(x) as long as x' E (2)),, as their net utility is 1 - cost(z, (z, x²) >> O. We can further incorporate worst-case tiebreaking by defining (1) to only consist of points with f (x')= = O.
PAC-learning with improvements is defined similarly to standard PAC-learning but for the above loss that incorporates agents' movements. A learning algorithm A has access to a training set consisting of m samples S E x drawn i.idd from fixed but unknown distribution D over X' and labeled by the ground truth f*. The learner's population loss is LOsSp(h, f*) = PEED [Loss (x: h, f"] Most of the results of this paper focus on the realizable setting in which f E H and for which can define PAC-learnability as follows:
Definition 2.2. [5, Definition 2.2] A learning algorithm A PAC-learns with improvements a concept class H. with respect to improvement function A and data distribution D with sample complexity m = ms 5; A, H. D) for any f E H and E, >> O, the following holds: with probability at least 1 8, takes in as input a sample S Ltd. Dmm labeled according to f and outputs h X -> >{0,1 13 such that LOSSp f*) S
3 Characterizing proper PAC-learning with improvements for any improvement function
In this section we prove complete characterization of which concept classes are properly PAC- learnable with improvements for any improvement function A. Our main conceptual advance is establishing a connection between PAC-Icarnability with improvements and the minimally consistent property that characterizes PAC-learnability with one-sided error [48, Chapter 2.4]. For discussion on the previous results on proper PAC-leariig with improvements which our theorem generalizes. see Appendix B. We first review relevant background on learning with one-sided error.
Definition 3.1. An algorithm A learns a concept class H with one-sided error if A PAC-learns H and the concept oulput by A does not have false positives.
For concept f, denote by graph(f) the set of all examples for f. namely {(,, f(x))) Fex We say that f is consistent with a set of examples S c X' x y Sf C graph(f). Let S C graph(f) for some f E H. A concept g E H the least g H. consistent with S if g is consistent with S and for all h E H consistent with S, every instance classified positive by is also classified positive by h. Note that a least g may not exist. concept class H is minimally consistent if for each f E and each nonempty and finite subset S C graph(f), f), there exists least E H consistent with S. It is textbook result that minimally consistent characterizes learning with one-sided error.
Theorem 3.2. [48, Chapter 2.4] A concept class is PAC-learnable with one-sided error if and only if it is minimally consistent.
To characterize PAC-learnability with improvements, we subtly modify the minimally consistent property to exclude sets of examples that are all labeled positively. We only require H to be mini- mally consistent on subsets S that have at least one negatively labeled example, calling this asym- metric variant nearly minimally consistent:
Definition 3.3. A concept class H. is nearly minimally consistent if for each f E H. and each nonempty and finite subset S C graph(f) (f) that contains at least one negative example (a, 0) E S. there exists least g H. consistent with S.
Our main result is that the new nearly minimally consistent property we define above exactly char- acterizes PAC-Iearnability with improvements:

---

Algorithm 1: Proper learning with improvements
Input: Set S consisting of m i.i.d. sampled instances (11,,1),.... ... (I'm ym
I: if there exists such that yi = 0 then
2: Output: Least concept in H consistent with S
3: else
4: Output: Any concept in H consistent with S
5: end if
Theorem 3.4. A concept class H is properly PAC-leurnable with improvements for all improvement functions and all data distributions 'D with sample complexity m O (² (dvc(H) + log b)) if and only H has finite VC-dimension and is nearly minimally consistent.
Proof sketch. We discuss the conceptual ideas needed to prove Theorem 3.4, relegating the full proof to Appendix B. To learn with one-sided error, we output conservative classifier, namely the minimal concept that is consistent with the training set S, because we cannot afford any false positives. In learning with improvements however, "improve" to them. Assuming a worst-case improvement function A, the only case where points in S do not move any false positive is when they were originally positively labeled. In other words, false positives are allowed only if S consists of only positive labeled examples. It turns out that learning with improvements such S is easy: if we see only positive examples in the training set, with high probability the target concept f originally consisted almost entirely of positive labels under D. In this case we can simply output any concept consistent with S achieve low error. Our learning rule is given in Algorithm 1.
have false positives long points in S do not
Our theorem for proper PAC-learning with improvements the realizable setting and its relation to the previous results from Attias et al. [5] as well as to learning with one-sided error can be neatly summarized using Venn diagram (Fig. 1). The following two examples show that each of the Venn inclusions is strict.
Example 3.5 (Separation between intersection closed and minimally consistent). Suppose X = [21 } and H. = (h1, h2) with hı (x1) 1, (12) = 0 and h2(x1) O, h2(22) = 1. Clearly h n f2 $ H so H. not intersection-closed Since knowledge of a single label tells us the target concept, there is at most one concept consistent with any non-empty set, H is minimally consistent.
Example 3.6 (Separation between minimally consistent and nearly minimally consistent). Let X = (21, 333 and consider a concept class H {h1, f2g ha), where h₂(x;) i,j E (3]. Note that 7 is not minimally consistent since there is no least hypothesis E 7 consistent with S {(211 1)]. However, one can show that H nearly minimally consistent, the idea being that these singleton sets S only contain positive examples and hence it is not required for a least consistent with S exist. One can also show that H. is PAC-learnable with improvements.
ji + j] for all
Importantly, our results establish that PAC-learaabliity with one-sided error implies proper PAC- learnabliiyy with improvements. Nonetheless, since the difference between the learning algorithms for these two settings lies only in what happens when the training set S has only positive labels, learning with improvements only slightly easier than learning with one-sided error.
Comparison with strategic classification. A natural question to ask is when a concept class is learnalle for any A in the strategic classification model, where A(x) denotes the set of points x' that z can misreport. Recall that in the strategic classification, since z can misreport as but not truly improve to any x' (z), the loss function is the following:
Loss(r; h, f*)
max 1 [h (x') f*)) (')
We claim that for any concept class in which there exists a concept such that greater than e fraction of the points have negative label and greater than E fraction have positive label, there is no algorithm that can PAC-learn for every A. order to get error at most e, the learning algorithm A must output hypothesis h that labels at least one point positive, say h(x4)) = 1. However, since greater than than e fraction of the points have negative label, if we take A(x) = X' for all x E X' then all negative points can misreport as I4, thus incurring strategic loss greater than e. We conclude that
5

---

Allias cl al. [5]
[Our work] exactly characterizes learnability with improvements
Not intersection-closee
+ universal negative point
Natarajan [48] characterizes learnability with one-sided emoor
Nearly
minimally consistent
Attias et al. [5]
Minimally consistent
Intersection- closed
Figure 1: Relation between property PAC-learnability with improvements, PAC-learnabiliiyy with one-sided error, and the nearly minimally consistent, minimally consistent, and intersection-closed properties, assuming that the concept class has finite VC-dimension.
PAC-learning for every A is impossible in the strategic setting unless all concepts either label all points in X' negative or all points in X' positive.
4 Improper PAC-learning with ball improvement sets
In this section consider improper learning with improvements. We first note that in order to get interesting results, we must make some assumption on the improvement function A. This is because show that any concept class that is improperly PAC-learable for all A must also be properly PAC-learnable, and we have already characterized proper PAC-lcarnability in Section using the nearly minimally consistent property. (Recall that proper learnability trivially implies improper learnability.) Indeed, if ((x) = X' for all x E X then the learning algorithm cannot make any false positives else every negative instance can "improve"
such false positive and incur a classification error. On the other hand, if (xx = {x} for all x E X then the learning algorithm cannot incur too many false negatives any false negative is unable to improve. These two examples show that we make no assumption on A, the concept class must be learnable with one-sided error, which implies that it is properly PAC-Icamable by our results in Section 3.
Therefore, in this section we will focus on PAC-learning of geometric concepts where X C CRd for some d and assume that the improvement function is ((z) {x' E X || - =1|2 Sr.. Eu- clidean ball with radius r. (Our learnability upper bounds hold more generally for any improvement function for which (xx) contains a ball of radius centered at ær.) The fa-ball improvement set is well-studied in the strategic classification literature [55] and corresponds to the agent being able to misreport each of their features by continuous and bounded amount. In Appendix C we construct concept class with finite VC-dimension that shows that proper learning under balball improvement sets is intractable in general, which motivates why we consider improper learning. In stark contrast to proper learning, in the improper setting we show that under a generative data assumption known as coverability that all concept classes PAC-learnable, and furthermore such distributions are learnable with the simple memorization learning rule (Algorithm 4).
Coverability asssumption. To state our main result, we first describe the coverability assumption, which was introduced by Balcan et al. [14] in the context of robust learning in the presence of small, adversarial movements in the feature space.
Definition 4.1. [14, Definition 1] A distribution D is (e, 3, N) >coverabble if at least 1- fraction of probability mass of the marginal distribution Dx can be covered by N balls B,,..., Bx in Bd of radius 1 and of mass P [Bx] 2 B.
Definition 4.1 means that one can cover most of the probability mass of the distribution with not too many balls. Coverability is important in many learning settings because it implies the following nice property: with enough samples from D, with high probability it will be the case that all but fraction of instances according to the marginal distribution Dx will be distance at most r from some sampled instance. In Appendix C we formalize this observation and also discuss its relation to the well-known doubling dimension of a distribution [22, 32].

---

Sample complexity upper bound. Our main positive result, proven in Appendix C, is that the memorization learning rule (Algorithm 4) can PAC-learn any distribution D for which the condi- tional distribution of positive instances are coverable:
Theorem 4.2. Let the fraction of positive labels according to D be a constant independent of and assume that D*x the conditional marginal distribution for positive instances, is (e. B, N) -
Then with probability least 1 1-%, a predictor learned using Algorithm 4 from m O | log 7
N
i.i.d. samples from DD has improvement loss (h, f*) S.
We remark that the the parameter 3, which is the probability mass of each ball, implicitly depends on the improvement radius r. For example, if the data distribution is uniform over a bounded set in Rd, then ball of radius r has probability mass proportional to rd. Interestingly, Theorem 4.2 requires only an assumption on the marginal distribution Dx and is agnostic to the labels and the concept class. In particular, it is possible to improperly learn concept classes with infinite VC dimension so long as Definition 4.1 is satisfied. Furthermore, is even possible to achieve zero ervor with high probability in many natural situations, which reinforces the conceptual advance that learning with improvements often yields lower generalization error than standard PAC-learning. For example, Proposition C.4 implies that if X C Ie has a finite diameter then X' is coverable with 0, resulting in zero error with high probability by Theorem 4.2.
Sample complexity lower bound. Even though the memorization learning rule is very simple, it is the best one can hope for under the coverability assumption. Formally, in Appendix C we prove a lower bound for the number of samples needed to improperly PAC-leam with improvements:
Theorem 4.3. There exists concept class H and (0, B, b) -coverable data distribution 'D such that Ω (1 log } samples are necessary achieve 3 improvement loss with high probability.
Note that our upper bound (Theorem 4.2) can be generalized to any improvement function where A(x) D (a' E Rdd | || - x||, S rr), namely the improvement region for any æ contains a ball of radius r. Additionally, our lower bound (Theorem 4.3) can be generalized to any improvement function where ((x) C {a' E Rdd || - =1I2 Sr} namely the improvement region for any x is contained ball of radius These two observations imply that results robust to the
exact shape of the improvement set. Since we should think of N in Theorem 4.2 of order θ (1) which corresponds to N balls each of mass 3 covering all but e fraction of the instance space X, Theorem 4.3 shows that Theorem 4.2 is tight up to logarithmic factors in 3. This implies that the very simple memorization rule learns with improvements with a near-optimal sample complexity in the improper setting under a coverability assumption.
Comparison with strategic classification. One interesting observation is that the memorization learning rule outputs predictor that has monotonically decreasing improvement loss as the improve- ment region enlarges. This is because there are no false positives, and if false positives improve they must do to point with ground-truth positive label. A larger improvement set gives false posi- tives weakly more points to improve to and hence can only reduce error. On the other hand, larger movement set in strategic classification is generally expected to increase error, as this gives more chances for a negative point to mimic positive point. For example, in an extreme setting where X' is bounded, the movement radius is large enough to cover the entirety of X, and there is least. one point with positive label, then every negative point incurs classification error.
5 Learning linear separators optimally under bounded noise
As mentioned in the introduction, there is large and growing literature that studies PAC-Iearning with different types of label noise [10]: random classification noise [23, 18, 26], Massart noise [7, 8, 31, 25, 28], malicious noise Kearns and Li [39], Klivans et al. [41], Awasthi et al. [6, 9], and nasty noise [21, 30, 12]. Our understanding of learning with noise in the presence of strategic or improving agents is far more limited. Braverman and Garg [19] study learning in the presence of strategic agents with feature noise but no label noise. In contrast, we focus here on label noise. We develop optimal algorithms for learning linear separators the improvements setting with bounded label noise under isotropic log-concave distributions.
7

---

Concretely, as before we have a distribution D over the points in X. However, the learner does not see perfect labels f (xx) in the training sample. Instead, the labels y E {0, 1} are given by a noisy ~ N. An example is when y comes from crowdsourced data, where one typically assumes that for any given x the majority of labelers, but not all of them, will label the point correctly. Formally, Faayes(2) (x) = sign(Elu x] 2 The bounded or Massart noise model has parameter V 1 corresponding to an upper bound on the noise of any point z, i.. v(x) [ [v * [aayes())) xx] S v. A special case is the random classification noise (RCN), where all the labels of all points are flipped by equal probability v < 2.2 or Exr[ + Faaes(=))] x]] V.
label distribution
In the presence of noise, the goal is to minimize the expected loss which modifies the loss (Fq. (2.2)) in the noiseless case by considering movement of the agent at to the point the reaction set A (1) which has the largest expected loss (expectation is over the noise as below):
LOSS (2; =
max Ey N [b (2') + v'). z'EAr (m)
General reduction to PAC-learning with noise. In Appendix D we show a general reduction from learning linear separators with noise in the improvements settings to learning with noise in the standard PAC-setting:
Theorem 5.1. Suppose the improvement region for each point x X =d is given by A(x)
{a' arccos((as (zz, x²)) I r} and H.. is the class of homogeneous linear separators H. = {z + sign(w"")) x)= w E J- Let 'D be an isotropic log-concave distribution over the instance space X, realizable by some Jiuyes E H. Suppose the learner has access to noisy labels with bounded noise v(x)= = =Ev[1[y + [Twyes(z)]] x] I V. Finally, suppose that for any E,8 E (0. 2) given access p(2, log }), there is a proper learner in the standard PAC-setting that outputs in with error at most u + e, with probability 1 - 8 over the draw of the sample. For any 5 (0. 2): noisy sample of size m m= ( ( logg is sufficient PAC-learn with improvements an improper classifier such that for any I E X, Loss f) = Prylu # Imyes (x)) with probability at least 1 - 5. That is, our classifier is Bayes optimal.
to a noisy sample of size
Proof sketch. Our overall idea is as follows. Suppose there is proper learning algorithm that attains low error rate given sufficiently many samples from the distribution. For nice data distributions (e.g. for uniform, Gaussian, or log-concave distributions), in the case of linear separators, small error implies small angle from the target concept fuaye [43, 10]. Our approach is to run these algorithms on sufficiently many samples such that the angle θ between flayes and the learned f is small relative to the agent movement budget r. Then we use f to construct a conservative (improper) classifier such that all agents between fayes and ff are able to move to get positively classified according to f. but there is no point classified negative by flayes but positive by f.
Instantiation for well-studied noise classes. Theorem 5.1 implies sample complexity bounds for
Bayes optimal learning with improvements in the presence of bounded noise by simply plugging in the corresponding sample complexity bounds from the standard PAC learning setting. For in-
stance, for RCN the sample complexity is well-known to be Ô ( [10], implying Ö ((I-20)
for optimal learning with improvements. Similarly, for Massart noise [44], Theorem 5.1 implies
a Ô P( 2012 sample complexity bound. Note that while prior work on standard PAC learning only achieves OPT + E, we achieve exactly OPT, the error of finyes (x))
Discussion. To the best of our knowledge we are the first to study and design classifiers for label noise when agents react to the classifier. As in Section 4, in the strategic improvements model we can achieve smaller error than standard PAC-learning for learning linear separators with noise, in this case reaching the Bayes optimal error. Braverman and Garg [19] study designing classifiers under feature noise. One surprising result of their work is that it sometimes possible for the classifier to achieve higher accuracy when the agents' features are noisy under strategic classification. This is counterintuitive because noisy features cannot help when there is no strategic manipulation. is an interesting open question whether feature noise can reduce error under improvements as well.
8

---

Algorithm 2: Realizable online learning: Risk-averse majority vote
Input: Concept class H. maximum degree of the graph Ag. I: Initialize +- H.
2: for 1,2,... ................................ do
3: For each node I, set
1,
if if T = 1H A H|)
|
0, otherwise.
4:
A+ + fa E A (x(1)) (x) (z) = =}.
5:
H' t {h H h(=') = for all x' E A+).
6:
if there is mistake, and (
0 then | 0, H + {h H h(xl))) 1).
7:
8:
Else, H - H H' end if
9:
10: If there is a mistake and (z(t)) = 1, H t {h E H h(z(0) = 0}.
11: end for
6 Online learning on a graph
Attias al. [5] study the sample complexity of learning with improvements in general discrete graph model in the statistical learning setting. Here we will study mistake bounds in the natural online learning version of their model. The nodes of the graph correspond agents (points) and the (undirected, unweighted) edges govern the improvement function, i.e. the agents can move to their neighboring nodes in order potentially improve their classification. Formally, let G (V, E) denote an undirected graph. The vertex set V = {z1...... In represents fixed collection of n points corresponding
finite instance space X. The edge set E S V x V captures the adjacency information relevant for defining the improvement function. More precisely, for given vertex E V. the improvement set of given by its neighborhood in the graph, i.e. (xx) = {a' e V (x.²²) E E). Let f V )) represent the target labeling (partition) of the vertices in the graph G.
In the online setting, for each round t 1.2,.... the learner prediction (t))) for all nodes. The true label f* (*((x(() is then revealed and the learner is said to suffer a mistake if there there is some x' E (xx(()) such that (x') * (*''). The learner only knows whether a mistake was made, without learning about x'. The goal of the learner is to minimize the total number of mistakes across all rounds. Our main contributions are new algorithms for online learning with improvements in both the realizable and agnostic settings. All proofs of theorems in this section are in Appendix E.
node (+)) V and must make
Realizable online learning. In the realizable setting, f" E H. the concept space consists of valid labelings that the leamer is allowed to output. In the standard learning setting (where agents cannot improve), the majority vote algorithm (which predicts using the majority label of consistent classi- fiers in H. and discards all the inconsistent classifiers at every mistake) achieves mistake upper bound of log H)) We first construct an example (Example E. where the majority vote algorithm can result in unbounded number of mistakes in the learning with improvements setting.
A risk- aveeeeerse modification of the majority vote algorithm, requiring certain super-majority for pos- itive classification, can avoid the unbounded mistakes by the standard majority vote algorithm. This in stark contrast the online learning algorithm of Ahmadi et al. [3] for the strategic classification setting, where a super-majority is used for negative classification. Another modification from stan- dard majority vote (see Algorithm 2) is a change the way classifiers are discarded when a mistake is made, taking the predictions on the neighboring nodes into account.
Theorem 6.1. Algorithm makes at most (Aa + 1) log [H] mistakes, where Dg is the maximum degree of a vertex in G.

---

Algorithm 3: Agnostic online learning: Risk-averse weighted majority vote
Input: Concept class H. maximum degree of the graph Ag. I: Initialize w/ = 1 for each h E H.
2: for t 1,2,... ... do
3: Wi f EnEn wh
4: For each node x, set
5: Wi t -hEM(m(0)==1 Wh
1, if, 2 Boti
Ag Wt.
(x)))) - otherwise.
6:
A+ + fo ((x(0) ((x)))
= H' E E H h(x²) = for all x' A+}.
(x)=
7:
8:
if there is mistake, and (x((0) = then
9:
If | 0, H, + {h E H h(r((1) = 0}, wh + wx/2 for each h H,.
10:
Else, w/ < w 2 for each E H'
11:
end if
12: If there is mistake and h: (x(0) 1, HTT + (1 E H h(x(1)) = 1), wn wn/2 for
each h H,T.
13: end for
Agnostic online learning. In the agnostic setting, we remove the realizability assumption that there exists a perfect classifier f" E H. Instead, will try compete with smallest number of mistakes achieved by any classifier in H. denoting this by OPT. Our online learning algorithm will be a risk-averse version of the weighted majority vote algorithm.
We maintain a set of weights {w,] E HH for each concept the concept space. Initially, wa = for each concept h H. Let W, denote the sum of weights of experts that predict a node x as positive in round f, and W Σn wy, denote the total weight. Then the risk-averse online learner predicts positive if W.+ 2 Ao+1 W, and negative otherwise. Finally, if there is mistake, then we halve the weights of certain classifiers (as opposed to discarding them in Algorithm 2).
Ag
Theorem 6.2. Let G be any graph with maximum degree Ag 2 1. Algorithm 3 makes ((2(AG
(OPT + log (Hl)) mistakes.
Mistake lower bounds. Finally, we show lower bounds on the number of mistakes made by any deterministic learner against an adaptive adversary both the realizable and agnostic settings.
Theorem 6.3. For any A there exist graph G with any maximum degree A. hypothesis class H. and an adaptive adversary such that any deterministic learning algorithm makes at least A OPT mistakes in the agnostic setting and A mistakes in the realizable selting.
The lower bound in Theorem 6.3 is against deterministic algorithms. If we allow for the use of randomness, it may be possible remove the factor of Ag in the statement of Theorem 6.2 by using a modified version of the Hedge algorithm similar to [3, Algorithm 3]. We leave this as an open question.
7 Conclusion
In this paper we study statistical learning under strategic improvements. We develop new algo- rithms for proper learning with any improvement function, improper learning with Euclidean ball improvement sets, learning with noise, and online learning, Our work opens up several exciting new future directions. For example, it would be interesting extend the learning with improvements model beyond the binary classification setting to multi-label and regression settings. This would have practical applications to any learning problem that involves several classes such as assigning credit scores or deciding loan amounts. Also, we can study learnability under label noise in strategic classification, as well as under feature noise in our improvements model.
10

---

Acknowledgments
This work was supported in part by the National Science Foundation under grants ECCS- ECCSS2216899, ECCS-2216970, and by NSF Graduate Research Fellowship.
References
Saha Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. The strategie perceptron. In Pro- ceedings of the ACM Conference on Economics and Computation (EC), 2021. 2021. pages 6-25.
[2] Saba Ahmadi, Hedyeh Beyhaghi, Avrim Blum, and Keziah Naggita. On classification of strategic agents who can both game and improve. In Proceedings of the Symposium on Foundations of Responsible Computing ( (FORC), 2022.
Saba Ahmadi, Avrim Blum, and Kunhe Yang. Fundamental bounds on online strategic classification. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 22-58, 2023.
Saha Ahmadi, Kunhe Yang, and Hanrui Zhang. Strategic littlestone dimension: Improved bounds on online strategic classification. A. Gloherson, I.. Mackey, D. Belgrave, A. Fan, U. Paquet, Tomerak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 101696- 101724. Curran Associates, Inc., 2024.
[5] Idan Attias, Avrim Blum, Keziah Naggita, Donya Saless, Dravyansh Sharma, and Matthew Walter. PAC learning with improvements. International Conference on Machine Learning (ICML), 2025.
[6] Pranjal Awasthi, Maria-Florina Balcan, and Philip M. Long. The power of localization for efficiently learning linear separators with noise. Proceedings of the sorty-sixth annual ACM Symposiun on Theory of Computing (STOC), 2014.
[7] Pranjal Awasthi, Maria-Floring Balcan, Nika Haghtalab, and Ruth Urner. Efficient learning of linear separators under bounded noise. In Conference on Learning Theory, pages 167-190. PMLR, 2015.
[8] Pranjal Awasthi, Maria-Florina Balcan, Nika Haghtalab, and Hongyang Zhang. Learning and 1-bit com- pressed sensing under asymmetric noise. In Conference Learning Theory, pages 152-192. PMLR, 2016.
[9] Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. Journal the ACM (JACM), 63(6):1-27, 2017.
[10] Maria-Florina Balcan and Nika Haghtalab. Noise in classification. In Beyond the Worst-Cass Case Analysis of Algorithmss, 2020.
[11] Maria-Florins Balcan, Mikhail Khodak, Dravyansh Sharma, and Ameet Talwalkar. Learning-to-leam non- convex piecewise-lipseee lipschitz functions. Advances in Neural Information Processing Systems, 34:15056- 15069, 2021.
[12] Frorina Balean, Avrim Blum, Steve Hanneke, and Dravyansh Sharma. Robustly-rcliable learners under poisoning attacks. Annual Conference Computational Learning Theory, 2022.
[13] Maria-Florina Balcan, Avrim Blum, Steve Hanneke, and Dravyansh Sharma. Robustly-reliable learners under poisoning attacks. In Conference on Learning Theory, pages 4498-4534, PMLR, 2022.
[14] Maria-Florina Balcan, Avrim Blum, Dravyansh Sharma, and Hongyang Zhang. An analysis of robustness of non-Lipschitz networks. Journal of Machine Learning Research, 24(1), January 2023. ISSN 1532-
4435.
[15] Maria-Florina Balcan, Steve Hanneke, Rattana Pukdee, and Dravyansh Sharma. Reliable learning in challenging environments. Advances Neural Information Processing Systems, 36:48035-48050, 2023.
[16] Robert J. Bloomfield. What counts and what gets counted. Available SSRN, 2427106. 2016.
[17] Avrim Blum and Donya Saless. Regularized robustly reliable learners and instance targeted attacks. arXiv preprint arXiv:2410. 10572, 2024.
[18] Avrim Blum, Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala. A polynomial algorithm for learning noisy linear threshold functions. Algorithmica, 22:35-53 52, 1996.
[19] Mark Braverman and Sumegha Garg. The role of randomness and noise in strategic classification. In Proceedings of the Symposium Foundations of Responsible Computing (FORC 2020), 2020.
11

---

[20] Michael Brückner and Tobias Scheffer. Stackelberg games for adversarial prediction problems. In Pro- ceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 547-555. Association for Computing Machinery, 2011.
[21] Nader Bshouty, Nadav Eiron, and Eyal Kushilevitz. PAC learning with nasty noise. Theoretical Computer Science, 288:255-275, 1999.
[22] Nader H. Bshouty, Yi Li, and Philip M. Long. Using doubling dimension to analyze the generalization of learning algorithms. Journal of Computer and System Sciences, 75(6):323-335, 2009. ISSN 0022- 0000.
[23] Tom Bylander. Learning linear threshold functions in the presence of classification noise. In Annual Conference Computational Learning Theory, 1994.
[24] Gautam Chandrasekaran, Vasilis Kontonis, Konstantinos Stavropoulos, and Kevin Tian. Learning noisy halfspaces with a margin: Massart is harder than random. Advances in Neural Information Processing Systems, 37:45386-45400 2024.
[25] Sitan Chen, Frederic Koehler. Ankur Moitra, and Morris Yau. Classification under misspecification: Halfspaces, generalized linear models, and evolvability. In Neural Information Processing Systems, 2020.
[26] Edith Cohen. Learning noisy perceptrons by a perceptron in polynomial time. Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 514-523, 1997.
[27] Lee Cohen, Yishay Mansour, Shay Moran, and Han Shao. Learnability gaps of strategic classification. In The Thirty Seventh Annual Conference on Learning Theory, pages 1223-1252 PMLR, 2024.
[28] Ilias Diakonikolas and Nikos Zarifis. A near-optimal algorithm for learning margin halfspaces with mas- sart noise. In Neural Information Processing Systems, 2024.
[29] Hais Diakonikolas and Nikos Zarifis. A near-optimal algorithm for learning margin halfspaces with mas- sart noise. Advances in Neural Information Processing Systems, 37:88605-88626 2024.
[30] Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Learning geometric concepts with nasty noise. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2017.
[31] Ilias Diakonikolas, Themis Gouleakis, and Christos Tzamos. Distribution-indeeendeent PAC learning of halfspacces with Massart noise. Neural Information Processing Systems, abs/1906. 10075, 2019.
[32] Travis Dick, Mu Li, Venkata Krishna Pillutla, Colin White, Nina Balcan, and Alex Smola. Data Driven Resource Allocation for Distributed Learning. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 662-671. PMLR, 20 22 Apr 2017.
[33] Ran El-ianiv and Yair Wiener. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 1 11(53):1605- 1641, 2010.
[34] Micah Goldhlum, Liam Fowl, and Tom Goldstein. Adversarially robust few-shot learning: A meta- learning approach. Advances Neural Information Processing Systems, 33:17886-17895, 2020.
[35] Nika Haghtalab, Nicole Immorlica, Brendan Lucier, and Jack Z. Wang. Maximizing welfare with incentive-aware evaluation mechanisms. In Christian Bessiere, editor, Proceedings of the Twenty-innth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 160-166, 7 Main track, 2020. International Joint Conferences Artificial Intelligence Organization.
[36] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters. Strategic classification. In Proceedings of the ACM Conference Innovations in Theoretical Computer Science, pages 111-122, 2016.
[37] Lily Hu, Nicole Immorlica, and Jennifer Wortman Vaughan. The disparate effects of strategic manipula- tion. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 259-268, New York, NY, 2019. FAT '19, New York, NY, USA, Association for Computing Machinery.
[38] Adam Tauman Kalai, Varun Kanade, and Yishay Mansour. Reliable agnostic learning. Journal of Com- puter and System Sciences,
September 2012.
[39] Michael Kearns and Ming Li. Learning in the presence of malicious errors (extended abstract). In SIAM Journal on Computing, 1988.
12

---

[40] Jon Kleinberg and Manish Raghavan. How do classifiers induce agents to invest effort strategically? ACM Transactions Economics and Computation, 8(4), October 2020.
[41] Adam R. Klivans, Philip M. Long, and Rocco A, Servedio. Learning halfspaces with malicious noise. Journal Machine Learning Research, (0:2715-2744) 2009.
[42] Tosca Lechner and Ruth Urner. Learning losses for strategic classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7337-7344, 2022.
[43] László Miklós Lovász and Santosh S. Vempala. The geometry of logconeave functions and sampling algorithms. In Random Structures and Algorithms, 2007.
[44] Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statisties, 2006.
[45] John Miller, Smitha Milli, and Moritz Hardt. Strategic classification is causal modeling in disguise. In Hal Daumé IIII and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 19, pages 13-18, PMLR, 2020. Proceedings of Machine Learning Research.
[46] Smitha Milli, John Miller, Anca Dragan, and Moritz Hardt. The social cost of strategic classification. In FACCT, pages 230-239. 2019.
[47] B. K. Natarajan. On learning boolcan functions. In Proceedings of nineteenth annual ACM symposium on Theory of computing (STOC), pages 304,,,4, 1987.
[48] B. K. Natarajan. Machine Learning: Theoretical Approach. Elsevier Reference Monographs, s.l., 1. aufl edition, 2014. ISBN 978-1-55860-1422
[49] Ronald L. Rivest and Robert Sloan. Learning complicated concepts reliably and usefully. In Proceedings of the Seventh AAAI National Conference on Artificial Intelligence, pages 635 640, 1988.
[50] Han Shao, Shuo Xie. and Kunhe Yang. Should decision-makers reveal classifiers in online strategic classification? In Forty-second International Conference on Machine Learning, 2025.
[51] Dravyansh Sharma. No internal regret with non-convex loss functions. Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 14919-14922 149177, 2024.
[52] Dravyansh Sharma and Arun Suggala. Offline-to-onliee hyperparameter transfer for stochastic bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 20362-20370, 2025.
[53] Yonadav Shavit, Benjamin Edelman, and Brian Axelrod. Causal strategic linear regression. Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119, pages 13-18, PMLR, 2020. of Proceedings of Machine Learning Research.
[54] Ravi Sundaram, Anil Vullikanti, Haifeng Xu, and Fan Yao. PAC-leamnngg for strategic classification. Journal of Machine Learning Research, 24(1), January 2023.
[55] Tijana Zmic, Eric Mazumdar, S. Shankar Sastry, and Michael I. Jordan. Who leads and who follows in strategic classification? Advances in Neural Information Processing Systems, 34, 2021.
13

---

A Discussion of related work
Our paper is related to several works studying learning in strategic and adversarial environments:
Strategic classification. Taking into account how utility-maximinn
agents can strategically
"game" the classifier is an important research area in societal machine learning [37, 46, 19. 1. 35]. The first papers in this area modeled strategic gaming behavior as a Stackelberg game [36, 20] where negatively classified agents manipulate their features to obtain more favorable outcomes
the benefits outweigh the costs.
Learning with improvements. Kleinberg and Raghavan [40] are the first to consider learning with improvements, which is when agents manipulate but also genuinely improve their features. Ahmadi et al. [2] consider a similar improvement setting and propose classification models that balance maximizing true positives with minimizing false positives. Prior work has studied the inherent learnability of concepts in the strategic manipulation setting [54, 27, 42] but not in the strategic improvement setting. Attias et al. [5] propose to study the statistical learnability of con- cept classes, the sample complexity of learning, and the ability to achieve zero-errop classification in the improvement setting. Haghtalab et al. [35] also study the sample complexity of learning in the presence of improving agents, but they optimize for social welfare by maximizing the fraction of true positives after improvement and primarily focus on linear mechanisms. In contrast, we focus on classification error in which false positives matter, leading to fundamentaly different properties of good classifiers.
Reliable learning. Learning with improvements is also related to reliable machine learning [49, 33] in which learner may abstain from classification to avoid mistakes. The goal in reli- able learning is to tradcoff coverage, the fraction of classified points, against classification error. The conservative classification paradigm that serves a basis for many of our algorithms also has a similar flavor to learning with one-sided error [47, 38] in which the learned classifier is not allowed to have any false positives. There connections between strategic classification and adversarial learning [54], but it remains an interesting open question if similar connections can be established between learning with improvements and adversarial learning [13, 15, 17].
Learning with noise. There is a large and growing literature that studies PAC-learning with different types of label noise [10]: random classification noise [23, 18, 26), Massart noise [7, 8, 31, 25, 28], malicious noise Kearns and Li [39], Klivans et al. [41]. Awasthi et al. [6], and nasty noise [21, 30, 12]. Recent work [29, 24] has developed optimal approaches for learning margin halfspaces with bounded label noise. Braverman and Garg [19] study learning in the presence of strategic agents with feature noise but no label noise. The problem of learning with noise in the presence of strategic agents is understudied and a very relevant direction for future work.
Online strategic classification. Ahmadi et al. [3, 4], Cohen et al. [27]. Shao et al. [50] study the problem of strategic online binary classification. Our discrete graph model for online learning is similar theirs, agents nodes that can potentially move to their neighbors, except that consider true movements that can change the agents' labels (as opposed to just their classification). This distinction leads to surprisingly different good online learners. Connections with adversari- ally robust online learning (e.g. Goldblum et al. [34], Balcan et al. [11], Sharma [51], Sharma and Suggala [52]) are less well understood, especially in multi-task and meta-learning settings.
B Characterizing proper PAC-learning with improvements for any improvement function
Prior work. Attias et al. [5] prove a sufficient condition for learnability based on a property called intersection-closed, which we define below.
Definition B.1 (Closure operator of set). For any set S C X and any hypothesis class H C 2 the closure of with respect to H. denoted by CLOS& 22x + 2X is defined as the intersection
of all hypotheses in H that contain S, that is, CLOS#(S)
h. In words, the closure of S
NEH.SCK the smallest hypotheses in H which contains S. (h: ::::::SC h) 0, then CLOSx(S) X.
Definition B.2 (Intersection-closed classes). hypothesis class H C 2 intersection-closed for all finite S C X, CLOSH(()) E H. In words, the intersection of all hypotheses in H containing an arbitrary subset of the domain belongs to H. For finite hypothesis classes, an equivalent definition states that for any hy, h2 E H, the intersection hy O h2 is in H. as well Natarajan [47].
14

---

There are many natural intersection closed concept classes, for example, axis axis-larallel d d-dimensional hyperrectangles, intersections of halfspaces, k-CNF boolean functions, and linear subspaces. Theorem B.3. [5, Theorem 4.7] Let H. be an intersection-close There a learner that PAC-learns with improvements H with respect to any funncvomentfunction A and any data distribution 'D given a sample of size O (a (dvc(H) + log ž)), where dyc(H) denotes the VC-dimension of H.
concept class on instance space X.
Attias et al. [5] also prove the following necessary condition for learnability:
Theorem B.4. [5, Theorem 4.8] Let H be any concept class on finite instance space X such that at least one point x' E X classified negative by all h E H (i.e. {a h(x) = 0 for all h E H} & (), and suppose H (x is not intersection-closed on X' {x'}. Then there exists data distribution D and an improvement function such that no proper learner can PAC-leam with improvements H with respect to A and D.
Note that Theorem B.4 only applies when there is point that is classified negative by all concepts in H. and says nothing about learnability when this condition does not hold. Our main result, Theo- rem 3.4, shows an exact characterization of which concept classes are properly PAC-learnable with improvements for all improvement functions which generalizes both Theorem B.3 and Theorem B.4,
Characterizing proper PAC-learnability with improvements. We prove Theorem 3.4.
Proof of Theorem 3.4. Note that if A(x) = { for all x then learning with improvements reduces to vanilla PAC-learning, so finite VC-dimension is necessary by the Fundamental Theorem of Sta- tistical Learning. Assuming now that H. has finite VC-dimension, we first show that if a concept class H is not nearly minimally consistent then there exists improvement function A and data distribution D for which H is not PAC-lcarnable with improvements. Let f E H and S C graph(f) be such that S contains negative example (x_,0) S and there is no least concept consistent with S. Let D be the uniform distribution over Sx and suppose that the improvement function is
X 0 otherwise.
x-
A (z
Suppose that learning algorithm outputs concept g E H. If g is not consistent with S, then either g(x_) = or g(x) = 0 for some x E S, x * x_. Since points in S other than x_ cannot move, such points cannot improve and hence g suffers constant error. Hence
assume that g is consistent with S. Since there is no least concept consistent with S, there exists a concept also consistent with S and a point x+ for which g(x+) very well been the target concept since 'D is uniformly supported on S for which both and h are consistent with. However, note that x_ can in the worst case "improve" x. since g(z+) = 1, but then outputting g suffers constant error since the ground truth is l((x4) = O. We conclude that any learning algorithm must suffer constant error on D for the improvement function A defined above.
1 and h((+)) O. Note that h could have
The other direction is to show that if a concept class H. is nearly minimally consistent then H. is PAC- learnable with improvements. The learning algorithm we use (Algorithm 1) is very similar to the one used to learn with one-sided error [48, Chapter 2.4]. However, we need to specify what concept consists of only positive examples, in which case there
the algorithm outputs when the training may not be a least concept consistent with the examples so far. In this case it turns outputting any concept consistent with the training set S will work. Informally, this is because if S consists of only positive examples, then with high probability it must have been the case that f positively labels nearly all points according to D. By the Fundamental Theorem of Statistical Learning, the concept hs output by the learning algorithm agrees with I' on nearly all of D, which also means that hy positively labels nearly all points. Since positively label points do not move, then hg has low error in the improvement setting as well.
We now give the formal proof. For number of samples m 0 (dvc(H) + log h)), we know, for example see [48, Theorem 2. that the concept hs output by the the learning algorithm satisfies PawD (x)(()) # (x)] < & with probability at least 1 for any target concept f E H. We split into two cases.
Case 1: PRED (f) = 1 1- 1-5. 5. Then the concept hy disagrees with f on at most
I fraction of points according to D, so IP (r))) (x) = 1) 2 1 e. Such
15

---

are positively classified so they do not move and hence incur zero improvement loss. We conclude that with probability at least 1 è the improvement loss is at most e.
2
Case 2: PRED (=) = 1| s 1 1-1-
2- Then after m samples, the probability that the training
set S consists of a negative example is at least 1- For any I E A' with hg(x)) = 1, I does not move and hence the improvement loss the same as the 0-1 loss [1s(2) * f (=)] For any x E X' with h5(x)) = O, suppose that z moves to point x', possibly equal to If x'
then the improvement loss is again the same as the 0-1 loss. Otherwise we can assume x' * I, which means that hs(x')
1 since only moves if it can improve. If (*) = then the loss 1 [/s((a f [x')] is at most the 0-1 loss 1 [bs(() + ['(x]] = 1. Finally, we can assume / (a:) = 0. Since S consists of negative example, his is the least concept consistent with S, so lis(a') = = (x)) = which case x has zero improvement loss. By the union bound, with probability at least 1 the improvement loss is at most 5-
In both cases we conclude that with probability at least - ô the improvement loss is at most
C Improper PAC-learning with ball improvement sets
Proper learning with ball improvement sets is intractable. We construct simple concept class that has finite VC-dimension but is impossible to properly PAC-learn under by-ball improvement sets.
Example C.I. Consider union of two intervals, which clearly has finite VC-dimension. Let the instance space X be [0, 1), let H {hg habe (x) = iff x [2, U(b, }]}. and let 'D be the uniform distribution over [0, 1). Let r 2 and consider a target function f = ha with b chosen uniformly in (1: 2).
For any learning algorithm, with probability I the learner will not see the point b in its training data, so it learns nothing from training data about the location b. Note that ", -=)=0,
the other hand, we claim that for any other h = h4 E H we have Loss 2 1 4' Without loss
of generality assume b S }. Note that in the worst-case, all points S 4- which are negatively labeled, will move to b, incurring loss at least 1.
Covering lemma. We formally state and prove that with enough samples from D, with high prob- ability it will be the case that all but fraction of instances according to the marginal distribution Dx will be distance at most r from some sampled instance.
Lemma C.2. [14, Theorem 4.4] Suppose that Ti...., I'm m instances i.i.d. sampled from the marginal distribution Dx- D is (e, B, -ooeerbbbll,, for sufficiently large m = Q2 log N with probability at least 1 over the sampling we have IP [ B(x,, r) 2 1 -
For completeness we provide proof of the covering lemma from Balcan et al. [14].
Proof of Lemma C.2. Fix ball B; in the cover from Definition 4.1. Let B, denote the event that no point is drawn from ball B, over the m samples. Since successive draws are independent and by definition Ppx [B]] 2 3, we have
P B. <1 3) < exp(-Bm).
By union bound over N balls we have
F UB. SN exp(-8m) S
for m 2 1 log N. Therefore, with probability at least 1 - we have
N
N
U B(a.r) 1=1
U BA = P
U i=1
B(x,, r)
2 P
U
B 2
-
k=1
since for all A E [N] there is sample Nny By and By is a ball of radius 5
16

---

Algorithm 4: Memorization learning rule
Input: m instances (#' y.),...,
...,....6. (Fm, Um)
1: Initialize h(()) 0 for all Rd
2: for i 1,..., m do
3: If yy 1, set hxx;)
4: end for
Output: /
Doubling dimension. The coverability property of a distribution is closely related to the well- known notion of doubling dimension of a metric space [22, 32j.
Definition C.3 (Doubling dimension). A measure Dx has doubling dimension d' if for all points I E X and all radi r > O, we have Dx(BB(z 2r)) < 2 (D)(B(xrr))
Note that the uniform distribution on Euclidean space IR has doubling dimension d' = (d). Dou- bling dimension of a data distribution has been used to obtain sample complexities of generalization for learning problems [22] as well as to give bounds on cluster quality for nearest-neighbor based clustering algorithms in the distributed learning setting [32]. In our context, X' having finite doubling
dimension and finite diameter is enough to yield complete coverability (E = 0 in Definition 4.1).
Proposition C.4. [14, Lemma 4.7] Let X C Rdd have diameter D and doubling dimension d' (d). For T N. there exists a covering of X with N S (2D) balls of radius D 2
Memorization learning rule. For completeness we provide pseudocode for the memorization learning rule (Algorithm 4).
Sample complexity upper bound. We prove Theorem 4.2.
Proof of Theorem 4.2. The idea is that with enough samples every ground-truth positive instance in ball has sampled positive instance in the same ball that it can improve to. We first claim that h
incurs zero improvement loss on points x for which f*)x) = O. Since h(z')= = = f*(x') = 1
by definition of the memorization learning rule, we must have h(x)) O. If there exists x' A(x) for which h(x') = 1, then æ will improve to some such x' which has h(x²) = (x') = 1. If there no such z', then x stays put and h(z) fx) = O. Hence we only need consider points for which (*) = 1. If h(x) = 1 as well then does not incur error. For all other points x for and (x( = namely the false negatives, due to the coverability assumption we claim that for all but e fraction of these points there will exist positively labeled sample in every
which h(x)
ball that x can improve to. Let balls Bi.... BN each with radius and mass PD; [Bx] 2 3 cover
O f1 log )) samples, with probability least
Dz- Then by Lemma C.2, after
7 there
will be at least one positively labeled sample in every ball Br. This implies that least 1 - e fraction
of points x E D are within distance of sampled positive instance x' E A(x), f(x))=(()))))))))))(() 1. All such z can improve to x' and hence Loss(h, f*) I as desired.
Sample complexity lower bound. We prove Theorem 4.3.
Proof of Theorem 4.3. Consider data distribution D that consists of N distinet points each with probability mass (3 such that the pairwise distance between points is greater than the improve- ment radius Let the concept class H consist of all 2 possible labelings of these N points, with the rest of H being labeled negative. By construction D is trivially (0,83 8, -coverable. We claim
that sampling every point is necessary to achieve error. Assume for contradiction that there is an unsampled point z=. Since 76 consists of all possible labelings of the points, x" could be labeled negative or positive. Let i be the predictor that the learning algorithm A outputs and let f be the ground-truth concept. We consider two cases. If the predictor h does not label any point with || - x=1 1=112 S positive, then x" misclassified when (x*)) = 1 since there no point in A(x*) that x" can improve to. Otherwise, the predictor h labels some point with ||æ z" s"ll2 positive.
17

---

Then when f*xx)) = 0, x" will move to z, but the ground truth is (x) = 0 and hence x" will be misclassified. Both cases yield contradiction if there an unsampled point, thus proving the claim. By standard coupon-collector analysis, = ( log N) log samples are necessary to sample every point.
D Learning linear separators optimally under bounded noise
General reduction to PAC-Iearning with noise We prove Theorem 5.1.
Proof of Theorem 5.1. Suppose we are given a noisy sample S with bounded noise S v. To con- struct the classifier in the improvements setting, we start with classifier h H that achieves low excess error in the standard PAC-learning setting. Using a well-known property of bounded noise (see e.g. Section 5.1 in Balcan and Haghtalab [10]), the disagreement of with the Bayes optimal classifier fayes can be upper bounded as
Pr(i(x) * Sayye (x)) - 2v
D
Now, for D isotropic and log-concave, this further implies [43, 10] that there absolute constant C' such that
Cs
8(h, huyes) S C (.r(((())) + flaye(()) S 1 2n'
where (h1, h2) is angle between the normal vectors of the linear separators h and h2. We set 0 Cs
1-2u = and define H. = {h E H 0(h, h)) S 0}. Note that ftnyes (z) E H. Now, we define P = {x X h(x) = for each E H}. the positive agreement region of classifiers in H. We set our improper classifier f = 1 | E PJ. We will now bound the error LOSSD. of the above classifier in the improvements setting. Note that if f(x) = 1 then fanyes construction. These points do not move and the error equals Prwlffoaes (I) & v).
by the above
If [(x) = O, we have two cases. Either, there is a point x' with arccos (I, x²)) S and f(x') 1. In this case, the agent moves to some such x'. But since fax')
we also have Jhayes (x') 1 and again Pry/e">/l((""" # v1 = pry - [/hyesssssssss.ee (x') * v/. Else, the distance point x' satisfies arccos( (I, x²)) > Ô. Then, any E A (including Maays) must classify a as negative. In this case, the agent does move and again the error of í matches that of Bayes
to any positive
Put together, the above cases imply that for any point æ, Lossy(z;;) PrN (hnyess (x) + y).
E
Online learning on a graph
Standard majority vote algorithm fails learn with improvements. We construct an example where the standard majority vote algorithm can result in an unbounded number of mistakes in the learning with improvements setting.
Example E.1. Let G be the star graph, with leaf nodes .2.....2.o. for A > 2, and the center node TA+1. Let H (bi,..., h..). where
+l. 0,
h₂(2,)
otherwise (j = 1).
Let f" h1. The standard majority vote algorithm
majority vote to make the prediction at each node. At time 1 = 1, say the learner sees the center node x!!) &A+1- We have that
(1)) = -11 otherwise (j =A+1).
[1, if E [A].
The learner suffers mistake, as there is x' all the classifiers agree with f on x 1141 and no classifier is discarded. Thus, if the online sequence of nodes simply consists of repeated occurrences of the center node, that is, x(() x 1 for all 1, then the learner using the standard majority vote algorithm suffers a mistake every round.
such that f*(x') = but (()))2)) = However,
18

---

Mistake upper bound in realizable setting. We prove Theorem 6.1.
Proof of Theorem 6.1. Suppose there is a mistake on round If h (x.1)) f (x(0) 1, there is no mistake as the agent does not move at all. We consider three cases.
Case 1: If ( (x(1) 1. (x(1)) O, then the agent doesn't 't move, and discard classifiers _a Ag-1 |H]
h H that predict h(x()))= 1. Clearly, f is not discarded, and discard at least
classifiers that make a mistake on w Case 2: If (1((()))))))
0, f (x(())
O, then there must be some x' E A(x(1) such that
(x') 1, (x') O. This implies that for each such x', we must have Kh H
[(xx')
OH| < Ac+t- Taking a union over all neighbors in A+, we conclude that H 2 Ag+1-
[H]
/ (x:(0) 1, then the agent can potentially move. If does not move, then it must be the case that A O, else 2!!) would have moved and changed the predicted label to 1. In this case, we discard at least Ac+I classifiers h H that predict h(x(9) = 0. is however also possible that the agent moves and still makes a mistake. In this case, | > 0 but there is
Case 3: If 7. (x:1))
[H]
point x' A(x(!)) in the neighborhood of x01) such that (zx(1))
but algorithm discards H' the set of classifiers that predict positive
f (x(1)) O. In this all neighbors of (*), and as argued above, [H'] 2 -
Thus we discard at least a Ac+1 fraction of the classifiers on each mistake, implying the desired mistake bound. Indeed, since f never gets discarded and we are in the realizable setting, we
[H|
make M mistakes then (1-Aot1)
[7|] o, M
log [71] log (1-ad-1) (Ac log (H|. O
Mistake upper bound in agnostic setting.
We prove Theorem 6.2.
Proof of Theorem 6.2. The overall arguments are similar those in the proof of Theorem 6.1. Sup- pose there is a mistake on round t. We have the following three cases.
(x:(0) = 1, f (x:10) = 0. In this case, we halve the weights wy, for classifiers E H that predict (xx(0)) = 1. The reduction in the total weight We in this case is at least 2 2(A+1])
W Ag W.. That
2
is, W++1 S Wt 2(2ot1) W. S We (1 211+
(x())) = 0, f (x(()) = 0. Since the learner made a mistake, there must be some x' E A(x(1) such that (x)) = (x') = 0. For each such x', the learner predicted positive and so èg
W. ΣnERIMe))= wh 2 Dotl W,, or ΣnEHIA(E)) wh I Acti- Taking a union over all neigh- bors in At, we get ΣnEm wh W, | W.
AaFT Z W, Ao aatT Aati By Line 10 of
Algorithm 3, this implies that W.+1 < W, (AAFIJ
(x:00) 0, (² halve the weight of all classifiers that predicted negative on ,(1), Since (x(()) = 0 implies that WT
1. If the agent does not move, then | 0. In this case,
Ag W., Wet1 < W; (1- (T On the other hand, if the agent moves, then
A ||| > We discard H' and as shown in the previous case, W S Wt (1 (1- (1-2(A+1)):
Thus, in all cases when there mistake, W441 S W, (1- 2(A Thus, after M mistakes.
W. < [7|| (1 2(Ae11) M Since f" makes most OPT mistakes, have W. Z0FT Putting
together, ZUPT < HH|
( which simplifies to the desired mistake bound.
Mistake lower bounds in realizable and agnostic settings. We prove Theorem 6.3.
19

---

Proof of Theorem 6.3. The proof is analogous to [3, Theorem 4.7] which shows lower bounds under strategic online classification. For A we use star graph G with leaf nodes 21.... ................................ .AA for A > 2 and the center node Ja+1- Let H {h1.... .ii......hhl ha), where (,;);) = 1 and (, = 1 for all
other #
We first consider the agnostic setting. The proof idea is to construct an adaptive adversary that chooses an example that induces mistake every round, but such that every round all but at most one hypothesis from H can classify this example correctly. Formally, after the learning algorithm outputs the predictor (0)) at round / the adversary chooses the next example according to the following procedure:
Case 1: If ( (Ia+1)= = 1, then the adversary picks the labeled example (#1+1, 0) and ground- truth labeling
[1 i [A] 0 if -
((x)))
Since #A-11 does not move under (9 then (( fails classify 3a+1 correctly. On the other hand, every classifier h; E H classifies JA+1 correctly since under h, 2a+1 will move to the point x; which has positive label under both h2 and f"
Case 2: If 1/ (zz) 0 for all j E | + 1], then the adversary picks the labeled example (7A+1 +1, 1) and the ground-truth labeling f (x,) = for j E [A + 1]. Since all points have negative label under (1))) #5+1 cannot improve under (, so (() fails to classify Ia+1 correctly. On the other hand, every classifier h; H classifies ra+1 correctly since under h4, Ja+1 will move to the point 2, which has positive label under both h; and f*
1 for some [4], then the adversary picks the labeled example (xz, 0). Since I; does not move under (() then h()) fails classify zj correctly. On the other hand, every classifier h; E H for & j classifies zj correctly as negative since æj cannot improve.
Case 3: If 11
and (x²)
By the above analysis. (t) makes a mistake on the next example for all f. However, for each at most one hypothesis from H makes a mistake, implying that the sum of the number of the mistakes made by all hypotheses over all rounds is at most the current round number t. Since [H A by the pigeonhole principle there exists a hypothesis that makes at most 1 mistakes, so OPT s A implying that the number of mistakes made is f A OPT in the agnostic setting.
For the proof of the A 1 lower bound in the realizable setting, we the construction in the agnostic setting but restrict to = - rounds. The learning algorithm makes A 1 mistakes, but this point there still exists least one hypothesis that has made mistakes far, say h; for
i E [A]. Then the adversary can keep using h; as the ground truth for the first A - 1 rounds in the
above procedure so that the ground truth is still realizable after A rounds.
O
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims accurately reflect prior work and contributions of this work.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
fine to include aspirational goals motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
All limitations have been discussed in context.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification:
Full proof's are included and assumptions are clearly stated.
21

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: The main contribution is theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or the contribution it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation,
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
22

---

Answer: [NA]
Justification:
The main contribution is theoretical.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
moniidesCooeSubmiii
onPolicy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so No an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ /ttpp..c/ppublll. http:cccccppccccccccccccccccccct pttppppuuuiidsse.p.pppppppp guwdee/dd/ee/ /Codee/emmmdmdmmimi issiissiin ssionPolicy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specifyy all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The main contribution is theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The main contribution is theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
23

---

is OK to report 1-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: The main contribution is theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: : http///eeerpp/eeeeee/eee cc
Answer:
[Yes]
Justification:
We reviewed the NeurlPS Code Ethies.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Theoretical work with direct societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that improvement in the quality of generative models could be used to

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitiga- tion strategies (e-g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The main contribution is theoretical.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
allow for controlled use of the model, for example by re-
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The main contribution is thcoretical.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode thoooe com datasets has
curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
25

---

Answer:
[NA]
Justification: No new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: No crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No study over human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
26

---

LLM does not impact the core methodology, scientific rigorousness, or origi- nality of the research.
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: : /otp:/c//coeeeeeeeee/22///////// for what should or should be described.
27


Reviews:
[{"review_id": "pZffSAmEEu", "reviewer": "Reviewer_9Ssd", "summary": "This paper studies the problem of learning in settings where agents can take improvement actions that beneficially alter their features after observing a published classifier. These improvements are assumed to reflect genuine increases in quality, as opposed to adversarial manipulation commonly studied in strategic classification. The paper builds on prior work by Attias et al. (2025) and investigates several learning settings under this assumption, including proper PAC learning, improper learning with geometric constraints, learning under label noise, and online learning on discrete improvement graphs.\n\nKey contributions include a characterization of proper PAC learnability via a condition termed nearly minimal consistency, sample complexity results for improper learning under Euclidean improvement sets with a coverability assumption, algorithms for noise-robust learning achieving Bayes optimality under specific distributional assumptions, and mistake-bound guarantees for online learning in realizable and agnostic settings. The paper also draws connections to other models in the literature, including PAC learning with one-sided error and strategic classification.", "questions": "1. Can you formalize the interaction between the learner and agents using a Stackelberg framework, and explicitly define agent best responses?\n\n2. Please clarify how your model compares to strategic classification—can agents both game and improve, or are improvements enforced by assumption?\n\n3. Can you add examples that illustrate how your algorithms behave on simple input spaces (e.g., linearly separable data under improvements).\n\n4. Can you provide experimental results on synthetic or real datasets to validate your theoretical claims?", "limitations": "not beyond the weaknesses and questions", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. Addresses a learning setting distinct from adversarial manipulation by considering beneficial improvements.\n2. Provides formal characterizations and bounds in multiple learning paradigms.\n3. Extends prior work and resolves some theoretical questions.\n\nWeaknesses\n1. Lack of Game-Theoretic Modeling Clarity:\nThe paper does not explicitly present the learner-agent interaction as a Stackelberg game, nor does it characterize the agent’s best-response behavior given a published classifier.\nThere is no analysis or modeling of how agents decide to take improvement actions, or under what utility assumptions they operate.\n\n2. Limited Connection to Strategic Learning Literature:\nStrategic learning frameworks often distinguish between gaming and improvement actions. This distinction is not discussed, nor is there a clear explanation of when or why the improvement model applies instead of a more general strategic model.\n\n3. Illustrative Examples Missing:\nThere are no concrete examples or visual illustrations of key ideas (e.g., how classifiers behave under improvements, what consistency conditions mean, or how improvements affect learning performance), which makes some theoretical claims hard to interpret.\n\n4. No Empirical Evaluation:\nThe paper does not include experiments on real or synthetic data. As a result, it is unclear whether the theoretical findings lead to effective or robust learning performance in practice.\nThere is no evidence provided to support the practical efficiency, robustness, or scalability of the proposed algorithms.\n\n5. It is difficult to tell the difficulty/novelty of the proof techniques", "was_revised": true, "final_justification": "The reviewers have addressed most of my questions in the rebuttal", "rebuttal": "We thank the reviewer for their comments and address their questions and concerns below.\n\n1. Can you formalize the interaction between the learner and agents using a Stackelberg framework, and explicitly define agent best responses?\n\nAs stated in the introduction and Section 2, the formal model is the following: first the learner publishes a classifier $h$, and the agents best respond to this classifier by moving to an arbitrary point $x’$ in the improvement set $\\Delta(x)$ such that $h(x’) = 1$ since they want to be positively classified. The classification error is computed based on whether or not $x’$, the point that $x$ moved to, is actually positive according to the ground truth $f^* $. We assume adversarial tie breaking, that is if an agent can move to a point which gets them a positive classification $h(x’) = 1$ but without being truly qualified $f(x’)=0$, then it will prefer to do that. Note that this basic formulation itself is not novel: it was introduced by Attias et al. (ICML 2025), and they also establish the game-theoretic connection. \n\nIt is straightforward to view this in the Stackelberg framework. Simply set the utility of the agent to be $1$ at positive points $h(x)=1$, $0$ at negative points $h(x)=0$ and the utility of movement to a point $x'$ within  $\\Delta(x)$ is something in $[0,1]$. As an example, we could set the utility of movement to $\\mathbb{I}[x’ \\in \\Delta(x)] \\cdot h(x’) \\cdot \\(2 - f^* (x’)\\) / 3$. This utility is such that the agent has no incentive to move if either $\\mathbb{I}[x’ \\notin \\Delta(x)]$ or $h(x’)=0$, else it has a utility of $\\frac23$ for actually negative points $f^* (x’)=0$ and $\\frac13$ for actually positive points (so it moves in either case but prefers the former). Note that $\\Delta(x)$ is the set of points to which the agent $x$ would ever consider (or is able to) move to, and its incentives to move to a point $x’$ within $\\Delta(x)$ are governed by $h(x’)$ and $f^* (x’)$ as described above.\n\nConversely, our improvement set based abstraction can be used to model an arbitrary utility function as follows. The utility of being positive is $1$ and negative is $0$ (without loss of generality). Movements are associated with cost functions (negative utilities) for each $x\\to x'$ move, and costs outside of $(0,1)$ can be ignored (agent either always moves or never moves, irrespective of the classifier). We can define the set $\\Delta(x)$ to be the set of points where the cost is in $(0,1)$. Now the agent with $h(x)=0$ would want to move to a point with $h(x’)=1$ as long as it is within $\\Delta(x)$, as the net utility is $1 - \\text{cost}(x,x’)$, which is positive. We can further incorporate worst-case tie-breaking by defining $\\Delta(x)$ to only consist of points with $f^* (x)=0$. We are happy to add this equivalence as a remark (this is alluded to but not explicitly stated).\n\n2. Please clarify how your model compares to strategic classification—can agents both game and improve, or are improvements enforced by assumption?\n\nAs stated in the introduction, the agent can move to any point in the improvement set. We call this “improving” rather than “gaming” (the latter term is used in strategic classification) because the agent is genuinely changing their features. What do you mean by “improvements enforced by assumption”? It is not enforced that agents move, but naturally they want to be positively classified so they will of course move to a positive point. Finally, we respectfully disagree with the comment that there is limited comparison to the strategic learning literature and note that we have indeed compared all the results in our model to strategic classification. Every section of our results has a subsection/paragraph comparing the results to strategic classification and we have contextualized the differences in our results on learning with improvements with respect to learnability and algorithm design in strategic classification. See lines [178-186], [249-257], [303-310], [337-340] for example.\n\n3. Can you add examples that illustrate how your algorithms behave on simple input spaces (e.g., linearly separable data under improvements).\n\nYes, we will add these examples to the paper! It must also be specified what the improvement set is. As an example, in the linearly separable case with Euclidean ball improvement sets, our results in Section 3 and 4 demonstrate that a good classifier should be the smallest halfspace that contains all the positive training examples. If the improvement radius is at least the margin between negatively and positively labeled examples, then one can even get zero error by using this classifier.\n\n4. Can you provide experimental results on synthetic or real datasets to validate your theoretical claims?\n\nThis is a theoretical machine learning paper. The results in the paper establish upper and lower bounds on sample complexity and mistake bounds of learning with improvements, which we believe are not suitable to verify experimentally but rather through proofs. Our techniques may inspire future empirical research, for example more conservatively designed classifiers with respect to false positives, to achieve better empirical effectiveness in the presence of improving agents."}, {"review_id": "u3I1Loqclo", "reviewer": "Reviewer_dh1P", "summary": "This paper studies PAC-learnability in the learning with improvement setting, where the agent can improve their feature vectors after observing the hypotheses given by the learner. The authors provide new conditions for which concept class, data distribution is learnable under different conditions, and provide the corresponding learning algorithms. See the \"Strengths And Weaknesses\" for more discussion on the results.", "questions": "The questions are given in \"Strengths And Weaknesses\".", "limitations": "Please see \"Strengths And Weaknesses\" for more discussion.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths And Weaknesses\n---\n\nSignificance/novelty of the results:\n\nThis paper provides new and significant results for understanding PAC-learnable with impartments, including conditions for learnable concepts, learnable distributions, and more general settings. More specifically:\n\nWithout any assumption on the improvement function of the agents, the authors show that the necessary and sufficient condition for PAC-learnability with improvement is the concept class being nearly minimally consistent.\n\nAssuming the agents can only improve their decisions over a ball, the authors further show that there exists an algorithm that can learn any agent distribution if the conditional distribution of positive instances is recoverable. \n\nThe authors also consider the more general setting with label noise, and e construct optimal algorithms for learning linear separators. Finally, they also consider online learning with improvements for the discrete graph model, and provide algorithms with near-optimal mistake bounds.\n\n\nPresentation:\n\nThis paper is clearly written and though not very easy to follow. It would be great to shortly discuss/define things like minimally consistent in the introduction. \n\n\nQuestions and comments:\n\n\nFor the setting in ball improvement set discussed in section 4, if X is bounded, how is the improvement set defined for the points at the surface? Is it the interaction between X and Delta(x)? \n\nIn Definition 4.1,  D is (epsilon, beta, N) coverable if … radius r. why (epsilon, beta, N) coverable does not depend on r? (e.g., (epsilon, beta, N, r) coverable). Also, why do Theorems 4.2 and 4.3 not depend on r? What if r is infty then? \n\n\nTheorem 3.4 shows a necessary and sufficient condition for PAC-learnable with improvements. However, it seems to be transforming from one definition to another. While it is nice, I wonder if the authors could discuss what it implies? How does nearly minimally consistent help understanding PAC-learnable with improvements?\n\nPersonally, I think this paper would fit COLT or ALT more, but NeurIPS is also suitable.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and address their questions and concerns below.\n\n1. For the setting in ball improvement set discussed in section 4, if X is bounded, how is the improvement set defined for the points at the surface? Is it the interaction between X and Delta(x)?\n\nYes, it would be the intersection between $\\mathcal{X}$ and the ball of radius $r$ centered at $x$. We meant to write $\\Delta(x) = \\\\{ x \\in \\mathcal{X}, \\ldots \\\\} $, thanks for catching the typo!\n\n2. In Definition 4.1, D is (epsilon, beta, N) coverable if … radius r. why (epsilon, beta, N) coverable does not depend on r? (e.g., (epsilon, beta, N, r) coverable). Also, why do Theorems 4.2 and 4.3 not depend on r? What if r is infty then?\n\nThe parameter $\\beta$, which is the probability mass of each ball, implicitly depends on $r$. For example in real applications, if for example the data distribution is uniform over a bounded set in $\\mathbb{R}^d$, then a ball of radius $r$ has probability mass proportional to its volume, which is proportional to $r^d$. A larger $r$ (which you can think of as larger $\\beta$) actually makes the sample complexity better (the bounds in Theorem 4.2 and 4.3 scale with $1/\\beta$), and this can intuitively be seen as well since you can cover the space with less balls and you only need to sample a point in each ball. In the extreme case of $r = \\infty$, as soon as there is a positive example $x$ in the training set you can achieve zero error by outputting a hypothesis that is 1 on $x$ and 0 everywhere else, and all other points will improve to $x$.\n\n3. Theorem 3.4 shows a necessary and sufficient condition for PAC-learnable with improvements. However, it seems to be transforming from one definition to another. While it is nice, I wonder if the authors could discuss what it implies? How does nearly minimally consistent help understanding PAC-learnable with improvements?\n\nThe implication is that you can check whether a concept class is learnable with improvements by checking a concrete property of the concept class (nearly minimally consistent) unlike the definition of PAC-learnability which deals with all improvement functions and all data distributions. This is the same type of result as the Fundamental Theorem of Statistical Learning, which says that a concept class is PAC-learnable (defined over all data distributions) if and only if it has finite VC-dimension. We show in the proof of Theorem 3.4 that the sample complexity in learning with improvements is also governed by the VC-dimension, but in addition the concept class must be nearly minimally consistent to be learnable."}, {"review_id": "v53cwZKL2l", "reviewer": "Reviewer_Zw74", "summary": "* This paper extends the “learning with Improvements” framework (Attias et al., ICML 2025) to more general settings. \n* In the learning with improvements setting, feature-label pairs represent agents, which respond to deployed classifiers. Given classifier $h$, agents represented by a feature vector $x$ move to a point in their “improvement set” $x’\\\\in\\\\Delta(x)$ if their classification can be made positive ($h(x)=0$, $h(x’)=1$), and stay in place otherwise. True label $f^*(x’)$ is a function of the “improved” feature vector $x’$, and the classifier’s performance is measured according to its post-response accuracy, with worst-case tie breaking. A learning algorithm has access to a finite sample from a base distribution, and the goal is to prove statistical learnability.\n* The main theoretical result of Section 3 is a characterization: A class $\\\\mathcal{H}$ is PAC-learnable with improvements if and only if it is nearly minimally consistent - a variation of the known notion of minimal consistency, which characterizes PAC learnability with one-sided error.\n* Section 4 explores improper learnability when the improvement functions are the set of euclidean balls. The main positive result gives a learnability guarantee that depends on distribution coverability, and the main negative result provides a lower bound for the required training set size in the general case.\n* Section 5 explores the learnability of linear separators under bounded label noise, relating sample complexity of upper bounds for learning with improvements in this setting to bounds of PAC learnability in the bounded noise model.\n* Finally, Section 6 explores learning with improvements in the online discrete-graph setting, providing positive results for realizable and agnostic settings.", "questions": "* Is it possible to extend the characterization result in Section 3 to the non-realizable case?\n* How would the results change if the agent is not assumed to make the \"worst case\" choice among all points in $\\\\Delta(x)$?\n* Are there classes $\\\\mathcal{H}$ which do allow for proper learning under ball improvement sets?\n* What are the possible societal implications of the results, or in which way results can be extended to increase societal impact?", "limitations": "Relation to adjacent work is discussed, and questions that arise from the analysis are stated clearly.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* Significantly extends a set of recently published results in a meaningful way.\n* Presentation is clear and easy to follow. Helpful intuition for proofs is provided.\n* Relation to adjacent work is clearly explained, both formally and intuitively.\n\nWeaknesses\n* No empirical evaluation.\n* Possible societal impact is not discussed.", "was_revised": true, "final_justification": "The paper is very interesting, and the clarifications during the rebuttal were very helpful. I maintain my original score, and I believe that the paper can be further strengthened by expanding the discussion of possible societal implications.", "rebuttal": "We thank the reviewer for their comments and address their questions and concerns below.\n\n1. Is it possible to extend the characterization result in Section 3 to the non-realizable case?\n\nAs far as we know it is not possible to extend the result in Section 3 to the non-realizable setting. In general it seems hard to get results for agnostic learning in this model, but we are able to get a nontrivial agnostic learning sample complexity upper bound for the discrete graph model in Section 6.\n\n2. How would the results change if the agent is not assumed to make the \"worst case\" choice among all points in $\\Delta(x)$?\n\nThis is a promising direction for future work. Indeed we assume that the agent can make the “worst case” choice in order to make our results robust to the agent’s choice (since they don’t know which points are ground truth positive or negative). We did consider exploring what happens if the agent for example moves to a “random” positive point according to $h$, but this becomes hard to analyze mathematically especially if the improvement set is a continuous region and not discrete points.\n\n3. Are there classes $\\mathcal{H}$ which do allow for proper learning under ball improvement sets?\n\nTheorem 3.4 shows that any nearly minimally consistent concept class is properly learnable for all improvement sets and in particular Euclidean balls. This is actually a fairly broad set of concept classes, for example it includes (but is not limited to) all intersection-closed classes such as intervals on a line, rectangles in $\\mathbb{R}^2$, polytopes in $\\mathbb{R}^d$, etc.\n\n4. What are the possible societal implications of the results, or in which way results can be extended to increase societal impact?\n\nOne possible societal lesson from the results is that conservative classifiers perform consistently well when agents can improve. In particular, this means that when setting cutoffs, say for college entrance exams, it is often not harmful to increase the cutoff by a bit because qualified students will always be able to work a bit harder to meet it. On the other hand, it can be very harmful to have the cutoff even slightly below the true cutoff (something that is not usually a problem in standard PAC learning). Quantitatively the paper shows that you can even achieve zero classification error in the learning with improvements model."}, {"review_id": "fmm1lBNDVJ", "reviewer": "Reviewer_78PX", "summary": "This paper continues the study of the setting known as \"learning with improvements.\" Here, agents (i.e. instances of the example space) can react to a published classifier by moving to a new instance which is positively classified by the published classifier. Compared to \"strategic classification\", in the \"learning with improvements\" setting,  agents can genuinely improve in order to attain the desirable classification. The authors provide several contributions. They provide an exact characterization of proper learning with improvements in the realizable setting in terms of a variant of minimally consistent concept classes. In the improper setting, the authors characterize learnability with improvements under a mild generative assumption on the data distribution. Finally, the authors also provide results under label noise as well as in the online setting.", "questions": "Suggestions: \n1) I think it would be good to provide some more intuition about when the loss in Equation (2.1) is 1, especially in terms of false positives and false negatives. In particular, it seems like the loss is 1 as long as there exists a false positive in $\\Delta_h(x)$ or h(x) is a false negative. \n2) In lines 140-146, I think it would be helpful to define \"least consistent\" explicitly in terms of the support of a hypothesis $h \\in H$ defined as $\\supp(h) = \\{x: h(x) = 1\\}.$ That is, for a realizable sample $S$, a hypothesis $g \\in H$ is least consistent, if for every consistent hypothesis $h \\in H$, we have that $\\supp(g) \\subseteq \\supp(h)$. \n3) In lines 140-146 and Definition 3.3, I think it would be good to give some examples of classes that are minimally and nearly minimally consistent.\n4) $\\Delta_G$ in Theorem 6.1 needs to be defined (I think it's the max out degree)\n\nQuestions: \n1) Theorem 3.4 seems to be a qualitative characterization of proper learning with improvements. Is there a quantitative characterization? That is, what is the optimal sample complexity for learning with improvements? Is there a dimension that characterizes this? \n2) Perhaps I'm mistaken, but when learning with label-noise, the goal is still to obtain small population error with respect to the true labels (not the noisy labels). It's just that the labels in the training data are noisy. This makes me confused about the noisy loss function defined in Line 274. Why is the loss here in terms of the noisy labels? What does getting a loss of $1$ here mean?\n3) In Lines 193-194, are you claiming that proper learning is without loss of generality if $\\Delta$ can be anything? Are you claiming that there exists a choice of $\\Delta$ such that a class $H$ is improperly learnable with improvements if and only if it is nearly minimally consistent?\n4) The algorithms for online learning are deterministic. While this is fine in the realizable setting, in the agnostic setting, randomization is key to removing the multiplicative factor in front of OPT. Is there a natural way to randomize Algorithm 3 and remove the $\\Delta$ factor in front of OPT? If not, what is the barrier?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- This paper is well written and easy to follow\n- The problem setting is clean and practically relevant\n- In my opinion, the results are interesting and present a clear contribution to the learning theory community.\n\nWeaknesses:  No major weaknesses stand out to me. That said, I would appreciate it if the authors could address my questions/suggestions below, as there are a few places where I believe that readability can be improved.", "was_revised": true, "final_justification": "I maintain my positive score as the authors have adequately answered my questions.", "rebuttal": "We thank the reviewer for their comments and helpful suggestions (which we intend to incorporate in our revision), and address their questions and concerns below.\n\n1. Theorem 3.4 seems to be a qualitative characterization of proper learning with improvements. Is there a quantitative characterization? That is, what is the optimal sample complexity for learning with improvements? Is there a dimension that characterizes this?\n\nYes, the proof of Theorem 3.4 in Appendix B gives a quantitative characterization. The sample complexity is governed by the (vanilla) VC-dimension when the concept class is learnable at all with improvements. Specifically, when $\\mathcal{H}$ is nearly minimally consistent, the sample complexity is that same as that of vanilla PAC-learning: $O(\\frac{1}{\\varepsilon} (d_\\text{VC}(\\mathcal{H}) + \\log \\frac{1}{\\delta}))$  under the realizability assumption (see bottom of page 14), and this is tight because the same lower bond argument for vanilla PAC-learning also serves as a lower bound for learning with improvements (take the closure of the concept class to make it minimally consistent). On the other hand, when the concept class is not minimally consistent, the proof of Theorem 3.4 constructs an improvement function $\\Delta$ (recall that the definition of learnability in Section 3 is respect to every improvement function) and a distribution $\\mathcal{D}$ for which any learner (even computationally unbounded) suffers constant error, so the sample complexity is unbounded. (In particular, a concept class could have small VC-dimension and thus small vanilla sample complexity but if it is not nearly minimally consistent it is guaranteed to have unbounded sample complexity in the improvements model.) To summarize, while VC-dimension is not sufficient to guarantee learnability with improvements, when the concept class is nearly minimally consistent, the sample complexity is governed by the VC-dimension.\n\n2. Perhaps I'm mistaken, but when learning with label-noise, the goal is still to obtain small population error with respect to the true labels (not the noisy labels). It's just that the labels in the training data are noisy. This makes me confused about the noisy loss function defined in Line 274. Why is the loss here in terms of the noisy labels? What does getting a loss of $1$ here mean?\n\nGreat question. While it seems sensible to define the loss in terms of the true labels, the standard literature on bounded noise (e.g. Balcan and Haghtalab [2020], Diakonikolas et al. [2019]) define error as the expected loss of the classifier over the joint (noisy) distribution $\\mathcal{D}$ over $X\\times Y$, and the goal is to compete with the Bayes optimal classifier which predicts the most likely label for each point (the bounded noise is assumed to be less than $\\frac12$ so this matches the “true” label without noise) and whose expected error is given by \"OPT\" (which is no more than the noise upper bound $\\nu$). The guarantees in standard PAC learning with noise (i.e. with improving or strategic agents) are usually stated in terms of excess expected error over “OPT\" in terms of a loss function that includes an expectation over the noise. Specifically in our setting, in addition to following the standard PAC learning convention, we choose the expected loss as it has the following nice interpretation. In the noisy setting, whether an agent is truly qualified given features $x'$ is a random variable (as opposed to a deterministic function $f^* (x)$ in the noiseless setting), and we want our predictions to be accurate (even as the agents move) in expectation. A loss of $1$ means that there is some point $x’$ to which the agent can “improve” to (if negative, the agent stays put if $h(x)=1$) such that our prediction $h(x)$ is completely inaccurate (almost surely).\n\n3. In Lines 193-194, are you claiming that proper learning is without loss of generality if $\\Delta$ can be anything? Are you claiming that there exists a choice of $\\Delta$ such that a class $H$ is improperly learnable with improvements if and only if it is nearly minimally consistent?\n\nHere is a clearer wording of that paragraph that we just edited based on your feedback:\n\nWe first note that in order to get interesting results, we must make some assumption on the improvement function $\\Delta$. This is because we show that any concept class that is improperly PAC-learnable for all $\\Delta$ must also be properly PAC-learnable, and we have already characterized proper PAC-learnability in Section 3 using the nearly minimally consistent property. (Recall that proper learnability trivially implies improper learnability.) Indeed, if $\\Delta(x) = \\mathcal{X}$ for all $x\\in \\mathcal{X}$ then the learning algorithm cannot make any false positives or else every negative instance can \"improve\" to such a false positive and incur a classification error. On the other hand, if $\\Delta(x) = \\\\{x\\\\}$ for all $x\\in \\mathcal{X}$ then the learning algorithm cannot incur too many false negatives as any false negative is unable to improve. These two examples show that if we make no assumption on $\\Delta$, the concept class must be learnable with one-sided error, which implies that it is properly PAC-learnable by our results in Section 3.\n\n4. The algorithms for online learning are deterministic. While this is fine in the realizable setting, in the agnostic setting, randomization is key to removing the multiplicative factor in front of OPT. Is there a natural way to randomize Algorithm 3 and remove the $\\Delta$ factor in front of OPT? If not, what is the barrier?\n\nWe believe that it is indeed possible to give a randomized algorithm which achieves sub-linear regret (as opposed to $\\Delta_G \\cdot \\text{OPT}$ mistakes). One way to do this is to use a modified version of the Hedge algorithm (or EXP3 under bandit feedback) where we update the weights after $K$ rounds and use the all-negative classifier on one of every $K$ rounds (chosen uniformly randomly). This would be a conservative version of Algorithm 3 of Ahmadi et al. (2023), a difference being they use the all-positive classifier instead to incentivize the agent to not make a deceptive move (while we use a conservative all-negative classifier to keep the agent from trying to improve)."}]

Author rebuttal:

Meta-review: The paper extends the new line of work in learning with improvements by providing positive learnability results on Euclidean ball improvements and also in the presence of noise.

The reviewers found the results of the paper to be interesting and significant. They also found the paper to be written clearly, which is a plus for a theory paper. Hence, I think this would be a nice contribution to NeurIPS.

For the camera-ready version, I ask the authors to fix the statement of Theorem 3.4 to add the requirement of finite VC-dimension. I would also encourage authors to add a short discussion of societal impact and incorporate some of the responses from the rebuttal to clarify the paper (particularly responses to reviewers dh1P and Zw74).
Decision: Accept (spotlight)