As machine learning (ML) models are increasingly used in social domains to make consequential decisions about humans, they often have the power to reshape data distributions. Humans, as strategic agents, continuously adapt their behaviors in response to the learning system. As populations change dynamically, ML systems may need frequent updates to ensure high performance. However, acquiring high-quality human-annotated samples can be highly challenging and even infeasible in social domains. A common practice to address this issue is using the model itself to annotate unlabeled data samples. This paper investigates the long-term impacts when ML models are retrained with model-annotated samples when they incorporate human strategic responses. We first formalize the interactions between strategic agents and the model and then analyze how they evolve under such dynamic interactions. We find that agents are increasingly likely to receive positive decisions as the model gets retrained, whereas the proportion of agents with positive labels may decrease over time. We thus propose a refined retraining process to stabilize the dynamics. Last, we examine how algorithmic fairness can be affected by these retraining processes and find that enforcing common fairness constraints at every round may not benefit the disadvantaged group in the long run. Experiments on (semi-)synthetic and real data validate the theoretical findings.
Paper
Similar papers
Peer review
Summary
This paper investigates an intriguing problem regarding how machine learning models evolve during dynamic retraining using model-annotated samples, incorporating strategic human responses. The authors discover that it becomes increasingly likely for individuals to receive positive decisions as the model undergoes retraining, although the proportion of individuals with positive labels may decrease over time. To stabilize the dynamics, the authors propose a refined retraining process. They also examine how these retraining processes can impact algorithmic fairness and find that enforcing common fairness constraints in every retraining round may not benefit the disadvantaged groups in the long term. Experiments conducted on both synthetic and real-world data validate the findings of this study.
Strengths
1. The paper thoroughly analyzes how humans, acting as strategic agents, adapt their behavior in response to ML systems and how this behavior impacts the retraining process of ML systems. By formalizing these interactions and analyzing their long-term dynamics, the paper provides a theoretical foundation for understanding and predicting these complex interactions. This in-depth analysis helps uncover potential systemic issues and offers concrete theoretical support for improving models. 2. The paper not only identifies potential risks of retraining ML models with model-annotated data but also proposes an improved retraining method using a probabilistic sampler to enhance the quality of model-annotated samples. This method aims to stabilize the dynamics of acceptance and qualification rates, reducing classifier bias. The proposed solution is innovative and practical, helping to mitigate negative impacts in real-world applications. 3. The paper combines theoretical analysis with experiments on semi-synthetic and real data to validate the findings. The experimental results, which show consistent dynamics with theoretical predictions, enhance the credibility and applicability of the research. This approach ensures the reliability of the research findings by providing both theoretical and empirical support.
Weaknesses
1. While the conclusions of the paper help understand the impact of human strategic behavior on ML systems, many of these conclusions are somewhat intuitive and straightforward. For instance, the increase in acceptance rates and the potential decrease in qualification rates over time are logically reasonable but do not provide particularly new insights. Delving deeper into underlying mechanisms or revealing more complex interactions could make the research more innovative and impactful. 2. The scale of the datasets used in experiments is relatively small, which may not fully capture the complexity of system dynamics in large-scale data environments. 3. The paper primarily focuses on linear models and specific distributions. The research conclusions might not fully apply to non-linear models and complex data distributions.
Questions
See weaknesses
Rating
5
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
N.A
Summary
This paper addresses the dynamics of machine learning systems when retrained with model-annotated and human-annotated samples in the presence of strategic human agents. It explores how these dynamics affect various welfare aspects, including those of applicants, decision-makers, and the broader social context. The work emphasizes the potential risks and unintended consequences of retraining classifiers in strategic settings, emphasizing the complex interplay between agent strategies and ML system updates.
Strengths
The paper addresses an underexplored aspect of machine learning: the interaction of strategic human agents with ML systems over iterative retraining cycles. The incorporation of both model-annotated and human-annotated data into the retraining process, alongside the strategic adaptations of agents, presents a novel problem formulation.
Weaknesses
1. The theoretical results depend on assumptions that may not hold in more complex or varied real-world scenarios, and the Gaussian, German Credit, and Credit Approval datasets in the experiment violate some conditions in the theoretical analysis. This limitation may affect the generalizability of the results. 2. It would be beneficial to organize the experiments section of the main paper, providing a more detailed display of results related to the refined retraining process, which is a main contribution of this work. 3. The study primarily examines binary classification scenarios with only two outcome classes (e.g., admitted/not admitted). It would be beneficial if the authors could explore how their findings and methodologies might be applicable to more complex machine learning tasks, such as multi-class classification or ranking problems, which are more common in real-world settings.
Questions
Please see the weaknesses part.
Rating
5
Confidence
4
Soundness
4
Presentation
2
Contribution
3
Limitations
The authors have adequately addressed the limitations and societal impact.
Summary
The paper explores a scenario where a machine learning system retrains itself over time by collecting data generated through ML system annotation itself as well as human-annotated data while allowing the distribution of training samples to evolve over time. This evolution is influenced by the strategic behavior of samples that may be marked as positive by the system. Based on this model, the paper investigates the dynamic processes of several metrics, including acceptance rate, qualification, and classifier bias.
Strengths
1. The problem is well-motivated. 2. The high-level model construction is interesting. For instance, the model considers the sequential aspects of the problem and analyzes how certain metrics change over time, which is more realistic than previous works. 3. Additionally, the author incorporates 'systematic bias' into the modeling and discusses numerous real-world examples related to algorithmic fairness, an important topic for the community.
Weaknesses
1. Some aspects of the results seem trivial or straightforward given the assumptions in the model. (Please see my questions below.) 2. The writing could be improved, as some statements in the paper are confusing. (Please see my questions below.) 3. The figure size, legend, and overall organization could be improved. For example, in Figure 2, the blue and red dots in the legend are too small, making the figure difficult to interpret. Additionally, the y-axis legend in Figure 2 uses different scales, complicating comparisons.
Questions
1. Assuming $N \gg K$ and that strategic agents, using the output of the previous classifier, adapt to the classifier's outcome, it seems straightforward that the acceptance rate should increase. Could you clarify what the non-trivial or surprising aspect of Theorem 3.3 is? 2. To what extent does the conclusion/results in Theorem 3.5 hold for classifiers beyond linear ones? 3. In what situations can the convexity assumption in Theorem 3.5 be validated in practice? 4. What does the term *cumulative* density function exactly refer to in the statement of Theorem 3.5? The domain of a standard cumulative function should be $\mathbb{R}$ based on the usual definition. How, then, can it be restricted to a half-space $J \subset \mathbb{R}^d$ in Theorem 3.5? Is this a typo, or am I missing something? 5. Line 99: What does the continuity of $P(Y | X)$ means here when $Y$ takes values in $\{0, 1\}$? 6. Lines 187-188: Why does $\mathcal{S}{m,t-1}$ have a higher qualification rate than $ \mathcal{S}{t-1} $? Shouldn't that be the acceptance rate? Or am I missing something?
Rating
5
Confidence
3
Soundness
3
Presentation
3
Contribution
2
Limitations
The authors have discussed the limitations of their work.
Thanks for your reply. We apologize that our previous response regarding the high-dimensional case has some inaccurate statements. We present the precise analysis regarding all situations from 1-dimensional to high-dimensional ones and answer your questions. > Theorem 3.5 1. All our previous statements are precise for the **1-dimensional** setting where Gaussian, Beta, and Uniform distributions satisfy the conditions in Theorem 3.5; 2. Theorem 3.5 itself is precise for the high-dimensional settings. However, you are correct that the convexity of CDF for $X$ and $Y$ does not ensure the convexity of the joint CDF $(X, Y)$. Consider the simplest independent 2-dimensional distribution setting where $F_X, F_Y$ are convex in 1-d space, we can derive the Hessian of the joint CDF as: $\begin{bmatrix} F’’_X \cdot F_Y & F’_X \cdot F’_Y \\\ F’_X \cdot F’_Y & F_X \cdot F''_Y \end{bmatrix}$ The Hessian is PSD if $ F_X''(x) \cdot F_X(x) \ge F_X’(x)^2$ and $ F_Y''(y) \cdot F_Y(y) \ge F_Y’(y)^2$ hold for any $(x,y) \in J$, which is equivalent to say $log(F_X)$ and $log(F_Y)$ are convex functions. Thus, features with log-convex CDFs will satisfy the conditions in Theorem 3.5 such as the Uniform CDF and any CDF in the form of $F(x) = \lambda e^{\lambda x}$ if $\lambda \ge 1$. 3. However, as we stated, Theorem 3.5 is a sufficient condition. In the proof of Theorem 3.5 under high-dimensional distribution settings with feature $(X_1, ..., X_d)$, we can derive the same results if the joint CDF $F$ is convex w.r.t each coordinate $X_i$ in the full domain of $X_i$. This means a multivariate feature distribution will result in a decreasing qualification rate if each feature has convex CDF and they are independent. This is to say, If each variable satisfies Beta distributions with $\alpha \ge \beta, \beta = 1$, the results in Theorem 3.5 still hold. 4. Regarding the situation where multiple features are dependent, the analysis can be increasingly challenging. However, in practice, the decision-maker often uses domain expertise and dimension-reduction methods (e.g., PCA) to do feature selection first, preventing severe violations of independence. > The FICO score example Theorem 3.3 and 3.5 in the FICO score example can be interpreted as follows: the decision-maker sets the score threshold to give loans, but the qualification means whether they can repay the loans and this is hidden. Theorem 3.3 illustrates that the decision-maker will set a lower score threshold when retraining goes on (e.g., from 700 to 600), but the qualification rate (i.e., the proportion of agents who will repay the loans) decreases. “An applicant’s score is above the threshold but they are not qualified for the loan” happens since the decision-maker lowers the acceptance threshold due to the misleading information it gets during the retraining. This phenomenon is one of our main discoveries that has not been studied in previous literature. > Proposed modifications of the manuscript Taking all the discussions together, we are happy to make the following modifications to the content related to Theorem 3.5: (i) add the convexity condition w.r.t each coordinate $X_i$ as mentioned above; (ii) add the FICO example in the appendix to illustrate the use cases in practice; (iii) Add more detailed discussions on whether different distributions in high-dimensional space satisfy Theorem 3.5.
Dear Authors, Thank you for your response. Please address the points mentioned earlier in our discussion in the revised draft to clarify the scope and applicability of the model for the readers. Despite some limitations in the theoretical results that are important to note (as previously discussed), I find the model to have some interesting features, particularly its dynamic approach to strategic classification and the incorporation of model-annotated samples. The topic of strategic classification and the deployment of ML models in social domains is indeed important, and I believe the work has the potential to benefit the community. Please clearly discuss the limitations and applicability of the model, so that these can be addressed/improved in future research. Consequently, I am raising my score from 4 to 5 and also increasing my confidence score. Thank you for your detailed and thorough responses during the discussion period, which helped me to better understand your work. Sincerely, Reviewer
Thanks for your endorsement and for increasing the score. We appreciate your suggestions and will revise the draft as highlighted in our discussion.
Summary
This paper studies the effects of retraining machine learning (ML) models with data annotated by both humans and the models themselves, especially in social domains where human behavior is influenced by the ML systems. The authors explore how strategic human agents, who adapt their behaviors to receive favorable outcomes from ML models, can create feedback loops that affect the model's performance and fairness over time. The paper begins by formalizing the interactions between strategic agents and ML models. It shows that as agents adapt to the decision policies of the model, they increasingly receive positive outcomes. However, this becomes problematic where the proportion of agents with truly positive labels may decrease over time. To address this issue, the authors propose a refined retraining process designed to stabilize these dynamics. The authors analyze how fairness constraints imposed during each round of model retraining might impact disadvantaged groups in the long run. They find that enforcing common fairness constraints can sometimes fail to benefit these groups, highlighting the complexity of maintaining fairness in dynamic environments. The empirical section of the paper includes experiments on both semi-synthetic and real datasets. These experiments validate the theoretical findings, demonstrating that the proposed retraining process can mitigate some of the adverse effects of strategic behavior. The results show that while acceptance rates of agents tend to increase, the actual qualification rates may decrease under certain conditions, leading to a growing discrepancy between perceived and actual qualifications.
Strengths
- The paper addresses a critical and relatively unexplored issue in ML – the long-term impacts of retraining models in the presence of strategic human behavior. - The formalization of interactions between strategic agents and ML models provides a robust foundation for analyzing these dynamics. - The investigation into how retraining processes affect algorithmic fairness is an important contribution of this work - The use of semi-synthetic and real data to validate the theoretical findings strengthens claims of the study
Weaknesses
- The theoretical analysis depends on several assumptions, such as the monotone likelihood ratio property and the availability of perfect information about agent distributions, which may not hold true in all real-world scenarios. - The mathematical models and proofs are complex, potentially making it challenging for practitioners to implement the findings directly. - While the experiments support the theoretical findings, the datasets used might not fully represent the diversity and complexity found in real-world applications.
Questions
- Can you provide more empirical evidence or case studies to support the validity of the assumptions made in your theoretical analysis? - Have you considered using more diverse and larger datasets to validate your findings? How might the results change with different types of data? - How do you envision your findings being applied to other domains beyond college admissions and hiring? Are there specific adjustments needed for other applications?
Rating
6
Confidence
3
Soundness
3
Presentation
3
Contribution
3
Limitations
- The study mainly focuses on specific social domains like college admissions and hiring, and its applicability to other fields remains uncertain. - The proposed solutions, including the refined retraining process and fairness interventions, may not always be effective in practice. Real-world conditions can vary significantly from controlled experimental settings, which might affect the outcomes.
Dear Authors, Thank you for your response. I am currently reviewing your rebuttal and will have another reply to it. In the meantime, I am still unclear about the statement and conditions of Theorem 3.5. Could you please clarify the definition of "cumulative density function" as used in Theorem 3.5? It appears that the domain of this function is $\mathbb{R}^{d}$, given that it is assumed its restriction to a half-space in $\mathbb{R}^{d}$ is convex. If this is the case, could you also clarify what you mean by a function in $\mathbb{R}^{d}$ being decreasing, as mentioned in the proof of Theorem 3.5? Thank you, Reviewer
Thanks for your timely reply! You are correct that "non-decreasing" in lines 957-958 means for each dimension $x_i$ in a $d$-dimensional feature $x \in J$, $F_X, P_X$ are non-decreasing. We will modify this sentence in the proof to make it clear. $F_X$ itself is non-decreasing in each dimension because it is CDF. Note that $P_X$ is the derivative of $F_X$, so the convexity itself ensures $P_X$ is non-decreasing in each dimension when $x \in J$. Thanks again for your careful review and suggestions.
Dear Authors, Thank you for your response. Based on your answer, I assume that when you work with the cumulative distribution function (not "cumulative density function" as mentioned in line 228 of your draft), you compute the CDF coordinate-wise. Also, when you say a function on $\mathbb{R}^{d}$ is non-decreasing, you mean it is non-decreasing in each coordinate. Please clearly state these conventions in your work, as they are not unique or standard assumptions about functions or distributions on $\mathbb{R}^{d}$. On the same line, regarding the assumption that $P_{Y|X}$ is continuous (mentioned in line 99), please specify that you mean $P_{Y|X}(1 \text{ or } 0 \mid x)$ is continuous over $x$. Otherwise, the way you have it there may confuse the readers. Additionally, in line 140, the domain of $h_{t}$ should be $\mathbb{R}^{d}$ (not $\mathbb{R}$ as you have it)? Please clarify. Assuming the above, I still have some clarifying questions regarding the conditions in Theorem 3.5. As I understand it, you are working with linear models, so $\mathcal{J}$ would be a subspace of $\mathbb{R}^{d}$ (as it is the decision boundary of a linear model). In your rebuttal above, you mentioned that $\mathcal{J}$ could be $(-\infty, \mu)$. However, it seems to me that $(-\infty, \mu)$ cannot arise in the context of Theorem 3.5, as $(-\infty, \mu)$ is not a subspace of $\mathbb{R}$. Am I missing something here? With that in mind, could you please elaborate on why Gaussian distributions or Beta distributions satisfy the convexity conditions in Theorem 3.5 (as $\mathcal{J}$ could be any subspace of $\mathbb{R}^{d}$)? Thanks, Reviewer
Thanks for your follow-up. We address your concerns as follows. - We agree with your points in paragraph 1 and will be happy to modify our draft as you suggested. Also, you are correct on the definition of CDF and the domain of $h_t$, and we will correct the typo. - We kindly clarify that $J$ is not the **decision boundary** itself. In line 101, we define $f_t$ as the classifier from $\mathbb{R}^d \rightarrow$ {0,1} (not $[0,1]$) which directly maps the feature to the label. Therefore, $J =$ { $x|f_0(x) = 0$ } is actually the **half-space** (not a subspace) in $\mathbb{R}^d$ separated by the decision boundary as we write in Theorem 3.5. - With these clarifications, Gaussian and Beta distributions possibly satisfy Theorem 3.5 and we were using $1$-d cases as examples: (i) Gaussian example says when $f_0$ sets an admission threshold smaller than or equal to $\mu$, then the convexity assumption is satisfied because the CDF $\frac{1}{\sqrt{2\pi}}exp \frac{(x-\mu)^2}{2\sigma^2}$ is convex in $(-\infty, \mu)$ and $J \in (-\infty, \mu)$; (ii) Similarly, consider the CDF of the Beta distribution parameterized by $\alpha, \beta$, we can derive the sign of its second order derivative is the same as $(\alpha + \beta - 2) \cdot (\frac{\alpha-1}{\alpha+\beta-2} - 1)$. Then if $\beta = 1$ and $\alpha \ge \beta$, the second-order derivative will always be positive to ensure the convexity in its domain. Note that we do not say any Gaussian/Beta CDF will satisfy Theorem 3.5. Instead, these are examples that these distributions may satisfy Theorem 3.5. Based on our discussion, we are happy to emphasize that $f$ is the classifier again in Theorem 3.5 to avoid confusion and elaborate more on the examples (e.g., discuss the convexity of Gaussian/Beta CDF in more detail) in the Appendix.
Dear Authors, Thank you for the clarification. Let’s assume the half-space case as you mentioned. My other question still stands. I am particularly interested in higher-dimensional cases, as they are more relevant to real-world scenarios. For the sake of our discussion, we can restrict to $d=2$ or higher instead of $d=1$. Could you please comment on the conditions under which the convexity assumption of Theorem 3.5 holds for multivariate Gaussian or multivariate Beta distributions (as $\mathcal{J}$ could potentially be any half-space in $\mathbb{R}^{d}$)? Thanks, Reviewer
Thanks for your follow-up. We answer your question as follows. - For distributions with **convex** Cumulative Distribution Function in the entire 1-d domain (e.g., beta distribution with parameters $\beta = 1$ and $\alpha \ge \beta$, uniform distribution, exponential distribution), conditions for Theorem 3.5 always hold in multi-dimensional cases. For other distributions such as Gaussian, we admit that satisfying the conditions in Theorem 3.5 rigorously might be challenging in multi-dimensional cases. Consider a simple case of 2-d Gaussian $(x_1,x_2)$ with mean $(\mu_1, \mu_2)$ and $x_1$ and $x_2$ two independent Gaussian variables, the convexity holds when $x_1 < \mu_1$ and $x_2 < \mu_2$, i.e., convexity only holds on “half” of the half-space $J$, the condition in Theorem 3.5 does not hold. - Despite the difficulty of satisfying the conditions, we want to emphasize that these conditions are only sufficient but not necessary, which means the phenomenon shown in Theorem 3.5 might hold more easily in practice. Indeed, we provided sufficient empirical analysis to complement the theorem (as highlighted in line 239) which includes the situations you mentioned. Specifically, the Gaussian dataset used in experiments is high-dimensional, and the blue lines in Fig 5-6 show that the results in Theorem 3.5 hold well empirically; The features in the credit approval dataset conform Beta distributions which violate the convexity assumption, but Figure 11 in page 19 still shows a similar trend as theorems - In many practical scenarios of Strategic Classification, the decision-maker often aggregates agents’ features and makes decisions based on one-dimensional representation, and the agents directly change their features in that 1-d representation space. Typical examples include: (i) Large credit agencies such as FICO and Experian aggregate consumers’ features and then produce a single credit score, then consumers strive to increase the score; (ii) The standardized tests aggregate students’ abilities in different subjects and give a single score. Such scenarios have been widely used in previous literature (e.g., [14] and [61]). Under these settings, Theorem 3.5 can be regarded as applying to a 1-d situation and the convexity conditions are much easier to be satisfied rigorously. Finally, we hope to restate that our paper is the first to model the long-term impacts of model retraining with agent strategic feedback considering more practical scenarios with *model-annotated* samples. With a comprehensive analysis of welfare and fairness, we believe our findings can promote trustworthy machine learning and shed light on future work. Thanks again for your prompt reply. Please let us know if you have any other questions. Authors
Thank you for your response. I still have two questions related to your previous answer to better understand the limitations and applicability of your work. 1. Consider a distribution with a convex cumulative distribution function (CDF), and let $X$ and $Y$ be random variables with such a distribution. Could you please explain why the joint distribution of $(X,Y)$ satisfies the convexity condition of Theorem 3.5 in your work? I am particularly interested in the case where $X$ and $Y$ could be potentially correlated and possibly not identically distributed. 2. My initial impression was that the $d=1$ case might be less applicable to real-world scenarios. However, based on your above response, I have a follow-up question regarding this case. For example, consider a situation where FICO scores are used to decide loan approvals. Assuming each applicant has a single feature (their FICO score) and the classifier is a threshold on this score (as you work with linear classifiers), and all technical assumptions (e.g., convexity) are satisfied, could you please elaborate on what Theorems 3.5 and 3.3 imply from a strategic classification perspective? For instance, given that there is only one feature, how could it happen that an applicant's score is above the threshold but they are not qualified for the loan? Thanks, Reviewer
Thank you for your response and the efforts made to address the initial concerns. We appreciate the clarifications and the additional experiments you provided. However, some concerns remain regarding the alignment between the theoretical assumptions and the empirical data, especially with datasets that do not fit these assumptions. While the trends appear consistent, this misalignment could limit the practical applicability of the theoretical outcomes. Additionally, we would benefit from a more detailed exploration of the specific challenges encountered when adapting your theoretical results to more complex class distributions to fully appreciate the breadth and impact of your contributions. Therefore, I will maintain my current score.
Decision
Accept (poster)