Mistake, Manipulation and Margin Guarantees in Online Strategic Classification
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911816145174528 |
|---|---|
| author | Shen, Lingqing Ho-Nguyen, Nam Giang-Tran, Khanh-Hung Kılınç-Karzan, Fatma |
| author_facet | Shen, Lingqing Ho-Nguyen, Nam Giang-Tran, Khanh-Hung Kılınç-Karzan, Fatma |
| contents | We consider an online strategic classification problem where each arriving agent can manipulate their true feature vector to obtain a positive predicted label, while incurring a cost that depends on the amount of manipulation. The learner seeks to predict the agent's true label given access to only the manipulated features. After the learner releases their prediction, the agent's true label is revealed. Previous algorithms such as the strategic perceptron guarantee finitely many mistakes under a margin assumption on agents' true feature vectors. However, these are not guaranteed to encourage agents to be truthful. Promoting truthfulness is intimately linked to obtaining adequate margin on the predictions, thus we provide two new algorithms aimed at recovering the maximum margin classifier in the presence of strategic agent behavior. We prove convergence, finite mistake and finite manipulation guarantees for a variety of agent cost structures. We also provide generalized versions of the strategic perceptron with mistake guarantees for different costs. Our numerical study on real and synthetic data demonstrates that the new algorithms outperform previous ones in terms of margin, number of manipulation and number of mistakes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_18176 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Mistake, Manipulation and Margin Guarantees in Online Strategic Classification Shen, Lingqing Ho-Nguyen, Nam Giang-Tran, Khanh-Hung Kılınç-Karzan, Fatma Machine Learning Computer Science and Game Theory Optimization and Control We consider an online strategic classification problem where each arriving agent can manipulate their true feature vector to obtain a positive predicted label, while incurring a cost that depends on the amount of manipulation. The learner seeks to predict the agent's true label given access to only the manipulated features. After the learner releases their prediction, the agent's true label is revealed. Previous algorithms such as the strategic perceptron guarantee finitely many mistakes under a margin assumption on agents' true feature vectors. However, these are not guaranteed to encourage agents to be truthful. Promoting truthfulness is intimately linked to obtaining adequate margin on the predictions, thus we provide two new algorithms aimed at recovering the maximum margin classifier in the presence of strategic agent behavior. We prove convergence, finite mistake and finite manipulation guarantees for a variety of agent cost structures. We also provide generalized versions of the strategic perceptron with mistake guarantees for different costs. Our numerical study on real and synthetic data demonstrates that the new algorithms outperform previous ones in terms of margin, number of manipulation and number of mistakes. |
| title | Mistake, Manipulation and Margin Guarantees in Online Strategic Classification |
| topic | Machine Learning Computer Science and Game Theory Optimization and Control |
| url | https://arxiv.org/abs/2403.18176 |