12/5/24 | 4:15pm | E51-149
Fatma Kılınç-Karzan
Associate Professor of Operations Research
Tepper School of Business, Carnegie Mellon University
Abstract: 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, while having access to only the manipulated features. After the learner releases their prediction, the agent’s true label is revealed. While previous algorithms such as the strategic perceptron guarantee finitely many mistakes under a separability assumption on agents’ true feature vectors, we show that they fail to encourage agents to be truthful resulting in infinitely many manipulations. We show that promoting truthfulness is intimately linked to obtaining adequate margin on the predictions, and provide two new algorithms aimed at recovering the maximum margin classifier in the presence of strategic agent behavior in an online setting. We prove finite mistake and finite manipulation guarantees as well as convergence to max margin classifier for our algorithms for a variety of agent cost structures under minor assumptions. We also provide a generalized version of the strategic perceptron algorithm along with its mistake guarantees for different costs under some assumptions, and also establish the necessity of the assumptions from the earlier literature to guarantee its finite mistake bound. Our numerical study on real and synthetic data demonstrates that the new algorithms outperform previous ones in terms of number of mistakes, number of manipulations, and margin in various settings. This is joint work with Lingqing Shen, Nam Ho-Nguyen and Khanh-Hung Giang-Tran.
Bio: Fatma Kılınç-Karzan is a Professor of Operations Research at Tepper School of Business, Carnegie Mellon University. She completed her PhD at Georgia Institute of Technology in 2011. Her research interests are on foundations of convex optimization and structured nonconvex optimization. Her research is supported by NSF, ONR and AFOSR and has received the 2015 INFORMS Optimization Society Prize for Young Researchers, the 2014 INFORMS JFIG Best Paper Award, and an NSF CAREER Award in 2015 She is/has been an elected member on the councils of the Mathematical Optimization Society and INFORMS Computing Society, and is serving/has served on MOS Council and the editorial boards of MOS-SIAM Book Series on Optimization, MathProgA, MathOR, OPRE, SIAM J Opt, IJOC, and OMS.