2020

Invariant Risk Minimization Games

Ahuja, Kartik, Shanmugam, Karthikeyan, Varshney, Kush R. et al.

Understand

The standard risk minimization paradigm of machine learning is brittle when operating in environments whose test distributions are different from the training distribution due to spurious correlations.

Training on data from many environments and finding invariant predictors reduces the effect of spurious features by concentrating models on features that have a causal relationship with the outcome.
In this work, we pose such invariant risk minimization as finding the Nash equilibrium of an ensemble game among several environments.
By doing so, we develop a simple training algorithm that uses best response dynamics and, in our experiments, yields similar or better empirical accuracy with much lower variance than the challenging bi-level optimization problem of Arjovsky et al.

Built on

J. F. Nash, “Equilibrium points in n-person games,” Proceedings of the national academy of sciences , vol. 36, no. 1, pp. 48–49, 1950
1950
Earlier work this paper cites.
G. Debreu, “A social equilibrium existence theorem,” Proceedings of the National Academy of Sciences , vol. 38, no. 10, pp. 886–893, 1952
1952
Earlier work this paper cites.
I. L. Glicksberg, “A further generalization of the kakutani fixed point theorem, with application to nash equilibrium points,” Proceedings of the American Mathematical Society , vol. 3, no. 1, pp. 170–174, 1952
1952
Earlier work this paper cites.
W. Rudin, “Real and complex analysis (mcgraw-hill international editions: Mathematics series),” 1987
1987
Earlier work this paper cites.
D. Fudenberg and J. Tirole, “Game theory, 1991,” Cambridge, Massachusetts , vol. 393, no. 12, p. 80, 1991
1991
Earlier work this paper cites.
J. Pearl, “Causal diagrams for empirical research,” Biometrika , vol. 82, no. 4, pp. 669–688, 1995
1995
Earlier work this paper cites.
D. Fudenberg, F. Drew, D. K. Levine, and D. K. Levine, The theory of learning in games . MIT press, 1998, vol. 2
1998
Earlier work this paper cites.
Y. Freund, R. Schapire, and N. Abe, “A short introduction to boosting,” Journal-Japanese Society For Artificial Intelligence , vol. 14, no. 771-780, p. 1612, 1999
1999
Earlier work this paper cites.
H. Shimodaira, “Improving predictive inference under covariate shift by weighting the log-likelihood function,” Journal of statistical planning and inference , vol. 90, no. 2, pp. 227–244, 2000
2000
Earlier work this paper cites.
R. B. Ash, B. Robert, C. A. Doleans-Dade, and A. Catherine, Probability and measure theory . Academic Press, 2000
2000
Earlier work this paper cites.
S. Boyd and L. Vandenberghe, Convex optimization . Cambridge university press, 2004
2004
Earlier work this paper cites.
J. Hofbauer and S. Sorin, “Best response dynamics for continuous zero-sum games,” Discrete and Continuous Dynamical Systems Series B , vol. 6, no. 1, p. 215, 2006
2006
Earlier work this paper cites.
S. Ben-David, J. Blitzer, K. Crammer, and F. Pereira, “Analysis of representations for domain adaptation,” in Advances in neural information processing systems , 2007, pp. 137–144
2007
Earlier work this paper cites.
D. J. Garling, Inequalities: a journey into linear analysis . Cambridge University Press, 2007
2007
Earlier work this paper cites.
M. Sugiyama, T. Suzuki, S. Nakajima, H. Kashima, P. von Bünau, and M. Kawanabe, “Direct importance estimation for covariate shift adaptation,” Annals of the Institute of Statistical Mathematics , vol. 60, no. 4, pp. 699–746, 2008
2008
Earlier work this paper cites.
T. Hofmann, B. Schölkopf, and A. J. Smola, “Kernel methods in machine learning,” The annals of statistics , pp. 1171–1220, 2008
2008
Earlier work this paper cites.

Similar

A. Rahimi and B. Recht, “Random features for large-scale kernel machines,” in Advances in neural information processing systems , 2008, pp. 1177–1184
2008
Cited alongside, same era.
A. Gretton, A. Smola, J. Huang, M. Schmittfull, K. Borgwardt, and B. Schölkopf, “Covariate shift by kernel mean matching,” Dataset shift in machine learning , vol. 3, no. 4, p. 5, 2009
2009
Cited alongside, same era.
D. Janzing and B. Schölkopf, “Causal inference using the algorithmic markov condition,” IEEE Transactions on Information Theory , vol. 56, no. 10, pp. 5168–5194, 2010
2010
Cited alongside, same era.
E. Barron, R. Goebel, and R. Jensen, “Best response dynamics for continuous games,” Proceedings of the American Mathematical Society , vol. 138, no. 3, pp. 1069–1083, 2010
2010
Cited alongside, same era.
X. Glorot, A. Bordes, and Y. Bengio, “Domain adaptation for large-scale sentiment classification: A deep learning approach,” 2011
2011
Cited alongside, same era.
E. Bareinboim, C. Brito, and J. Pearl, “Local characterizations of causal bayesian networks,” in Graph Structures for Knowledge Representation and Reasoning . Springer, 2012, pp. 1–17
2012
Cited alongside, same era.
B. Schölkopf, D. Janzing, J. Peters, E. Sgouritsa, K. Zhang, and J. Mooij, “On causal and anticausal learning,” arXiv preprint arXiv:1206.6471 , 2012
Original
2012
Cited alongside, same era.
D. Janzing, J. Mooij, K. Zhang, J. Lemeire, J. Zscheischler, P. Daniušis, B. Steudel, and B. Schölkopf, “Information-geometric approach to inferring causal directions,” Artificial Intelligence , vol. 182, pp. 1–31, 2012
2012
Cited alongside, same era.
H. Ajakan, P. Germain, H. Larochelle, F. Laviolette, and M. Marchand, “Domain-adversarial neural networks,” arXiv preprint arXiv:1412.4446 , 2014
Original
2014
Cited alongside, same era.
I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” in Advances in neural information processing systems , 2014, pp. 2672–2680
2014
Cited alongside, same era.
J. Peters, P. Bühlmann, and N. Meinshausen, “Causal inference by using invariant prediction: identification and confidence intervals,” Journal of the Royal Statistical Society: Series B (Statistical Methodology) , vol. 78, no. 5, pp. 947–1012, 2016
2016
Cited alongside, same era.
Y. Ganin, E. Ustinova, H. Ajakan, P. Germain, H. Larochelle, F. Laviolette, M. Marchand, and V. Lempitsky, “Domain-adversarial training of neural networks,” The Journal of Machine Learning Research , vol. 17, no. 1, pp. 2096–2030, 2016
2016
Cited alongside, same era.

Then

Z. Lu, H. Pu, F. Wang, Z. Hu, and L. Wang, “The expressive power of neural networks: A view from the width,” in Advances in neural information processing systems , 2017, pp. 6231–6239
2017
Later among the works it cites.
S. Beery, G. Van Horn, and P. Perona, “Recognition in terra incognita,” in Proceedings of the European Conference on Computer Vision (ECCV) , 2018, pp. 456–473
2018
Later among the works it cites.
C. Heinze-Deml, J. Peters, and N. Meinshausen, “Invariant causal prediction for nonlinear models,” Journal of Causal Inference , vol. 6, no. 2, 2018
2018
Later among the works it cites.
S. Magliacane, T. van Ommen, T. Claassen, S. Bongers, P. Versteeg, and J. M. Mooij, “Domain adaptation by using causal inference to predict invariant conditional distributions,” in Advances in Neural Information Processing Systems , 2018, pp. 10 846–10 856
2018
Later among the works it cites.
S. Zhao, M. M. Fard, H. Narasimhan, and M. Gupta, “Metric-optimized example weights,” arXiv preprint arXiv:1805.10582 , 2018
Original
2018
Later among the works it cites.
J. Hoffman, M. Mohri, and N. Zhang, “Algorithms and theory for multiple-source adaptation,” in Advances in Neural Information Processing Systems , 2018, pp. 8246–8256
2018
Later among the works it cites.
J. Lee and M. Raginsky, “Minimax statistical learning with wasserstein distances,” in Advances in Neural Information Processing Systems , 2018, pp. 2687–2696
2018
Later among the works it cites.
Y.-P. Hsieh, C. Liu, and V. Cevher, “Finding mixed nash equilibria of generative adversarial networks,” arXiv preprint arXiv:1811.02002 , 2018
Original
2018
Later among the works it cites.
M. Arjovsky, L. Bottou, I. Gulrajani, and D. Lopez-Paz, “Invariant risk minimization,” arXiv preprint arXiv:1907.02893 , 2019
Original
2019
Later among the works it cites.
P. de Haan, D. Jayaraman, and S. Levine, “Causal confusion in imitation learning,” in Advances in Neural Information Processing Systems , 2019, pp. 11 693–11 704
2019
Later among the works it cites.
A. Subbaswamy, B. Chen, and S. Saria, “Should i include this edge in my prediction? analyzing the stability-performance tradeoff,” arXiv preprint arXiv:1905.11374 , 2019
Original
2019
Later among the works it cites.
H. Zhao, R. T. d. Combes, K. Zhang, and G. J. Gordon, “On learning invariant representation for domain adaptation,” arXiv preprint arXiv:1901.09453 , 2019
Original
2019
Later among the works it cites.
F. D. Johansson, R. Ranganath, and D. Sontag, “Support and invertibility in domain-invariant representations,” arXiv preprint arXiv:1903.03448 , 2019
Original
2019
Later among the works it cites.
M. Mohri, G. Sivek, and A. T. Suresh, “Agnostic federated learning,” arXiv preprint arXiv:1902.00146 , 2019
Original
2019
Later among the works it cites.
P. Mertikopoulos and Z. Zhou, “Learning in games with continuous action sets and unknown payoff functions,” Mathematical Programming , vol. 173, no. 1-2, pp. 465–507, 2019
2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…