Strategic Classification from Revealed Preferences

Our (Jinshuo Dong, Aaron Roth, myself, Bo Waggoner, and Steven Wu) paper Strategic classification from revealed preferences was just accepted at EC ‘18! Not only is it exciting that our work is being published, but this is also my first publication which, I think, officially makes me an academic. At the very least, my Erdős number is 4.

Our paper examines a setting in which self-interested agents interact with a machine learning model. Imagine you are designing a filter for an email system. There are two kinds of emails that might be sent: legitimate ‘non-spam’ messages which you want to pass through the filter, and spam messages which you would like to block. The challenge comes from how spammers and non-spammers respond differently to the filter system. A non-spammer does not think about her message as being caught by a filter, so she does not carefully craft her emails to skirt your system. In other words, she sends exactly the message she would like to send. Spammers, on the other hand, are aware of the filtering system and have to tweak their emails to evade your filter. The spammer has a message he would like to send, but he may have to modify it in order for it to pass through the filter. We model this change as incurring a cost to the spammers.

We consider this problem in an online setting. At each time step, you publish your spam filter, and you observe whether you correctly or incorrectly labeled a message sent to your system. You then get to adjust your filter. At the surface, this problem is really, really, really hard to solve. We only get to see the messages the spammers actually send, rather than the ones they wanted to send, and we don’t get to see the cost function a spammer used to inform his best-response to our filter. At the core, we want to deploy the spam filter which minimizes our classification error subject to the spammers trying to maximize our error on their examples.

In the paper we do two things: first, we demonstrate sufficient conditions for the optimization problem of choosing the best spam filter to be convex. Second, we present a modification of an existing optimization algorithm which gives us a no-regret online learning algorithm to deploy a sequence of filters. The paper is pretty technical, but if you’re interested, you can check out a preprint from the fall here, on the arXiv. For a precise, but less technical overview, we have a three-page ‘extended abstract’ [here], which appeared at the Workshop on Learning in the Presence of Strategic Behavior at NeurIPS ‘17.