nips nips2009 nips2009-161 nips2009-161-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Michael Brückner, Tobias Scheffer
Abstract: The standard assumption of identically distributed training and test data is violated when an adversary can exercise some control over the generation of the test data. In a prediction game, a learner produces a predictive model while an adversary may alter the distribution of input data. We study single-shot prediction games in which the cost functions of learner and adversary are not necessarily antagonistic. We identify conditions under which the prediction game has a unique Nash equilibrium, and derive algorithms that will find the equilibrial prediction models. In a case study, we explore properties of Nash-equilibrial prediction models for email spam filtering empirically. 1
[1] Gert R. G. Lanckriet, Laurent El Ghaoui, Chiranjib Bhattacharyya, and Michael I. Jordan. A robust minimax approach to classification. Journal of Machine Learning Research, 3:555–582, 2002.
[2] Laurent El Ghaoui, Gert R. G. Lanckriet, and Georges Natsoulis. Robust classification with interval data. Technical Report UCB/CSD-03-1279, EECS Department, University of California, Berkeley, 2003.
[3] Amir Globerson and Sam T. Roweis. Nightmare at test time: robust learning by feature deletion. In Proceedings of the International Conference on Machine Learning, 2006.
[4] Choon Hui Teo, Amir Globerson, Sam T. Roweis, and Alex J. Smola. Convex learning with invariances. In Advances in Neural Information Processing Systems, 2008.
[5] Amir Globerson, Choon Hui Teo, Alex J. Smola, and Sam T. Roweis. Dataset Shift in Machine Learning, chapter An adversarial view of covariate shift and a minimax approach, pages 179– 198. MIT Press, 2009.
[6] Tamer Basar and Geert J. Olsder. Dynamic Noncooperative Game Theory. Society for Industrial and Applied Mathematics, 1999.
[7] J. B. Rosen. Existence and uniqueness of equilibrium points for concave n-person games. Econometrica, 33(3):520–534, 1965.
[8] Anna von Heusinger and Christian Kanzow. Relaxation methods for generalized Nash equilibrium problems with inexact line search. Journal of Optimization Theory and Applications, 143(1):159–183, 2009.
[9] John M. Danskin. The theory of max-min, with applications. SIAM Journal on Applied Mathematics, 14(4):641–664, 1966. 9