2020

Empirical or Invariant Risk Minimization? A Sample Complexity Perspective

Ahuja, Kartik, Wang, Jun, Dhurandhar, Amit et al.

Understand

Recently, invariant risk minimization (IRM) was proposed as a promising solution to address out-of-distribution (OOD) generalization.

However, it is unclear when IRM should be preferred over the widely-employed empirical risk minimization (ERM) framework.
In this work, we analyze both these frameworks from the perspective of sample complexity, thus taking a firm step towards answering this important question.
We find that depending on the type of data generation mechanism, the two approaches might have very different finite sample and asymptotic behavior.

Built on

On learning invariant representation for domain adaptation
Original
Zhao, H., Combes, R. T. d., Zhang, K., and Gordon, G. J. (2019) · 1901
Earlier work this paper cites.
Invariant risk minimization
Original
Arjovsky, M., Bottou, L., Gulrajani, I., and Lopez-Paz, D. (2019) · 1907
Earlier work this paper cites.
Adversarial target-invariant representation learning for domain generalization
Original
Albuquerque, I., Monteiro, J., Falk, T. H., and Mitliagkas, I. (2019) · 1911
Earlier work this paper cites.
Probability and measure theory
Ash, R. B., Robert, B., Doleans-Dade, C. A., and Catherine, A. (2000) · 2000
Earlier work this paper cites.
Unshuffling data for improved generalization
Original
Teney, D., Abbasnejad, E., and Hengel, A. v. d. (2020) · 2002
Earlier work this paper cites.
Out-of-distribution generalization via risk extrapolation (rex)
Original
Krueger, D., Caballero, E., Jacobsen, J.-H., Zhang, A., Binas, J., Priol, R. L., and Courville, A. (2020) · 2003
Earlier work this paper cites.
Matrix analysis for scientists and engineers
Laub, A. J. (2005) · 2005
Earlier work this paper cites.
Representation via representations: Domain generalization via adversarially learned invariant representations
Original
Deng, Z., Ding, F., Dwork, C., Hong, R., Parmigiani, G., Patil, P., and Sur, P. (2020) · 2006
Earlier work this paper cites.
Analysis of representations for domain adaptation
Ben-David, S., Blitzer, J., Crammer, K., and Pereira, F. (2007) · 2007
Earlier work this paper cites.
In search of lost domain generalization
Original
Gulrajani, I. and Lopez-Paz, D. (2020) · 2007
Earlier work this paper cites.
Out-of-distribution generalization with maximal invariant predictor
Original
Koyama, M. and Yamaguchi, S. (2020) · 2008
Earlier work this paper cites.

Similar

Covariate shift by kernel mean matching
Gretton, A., Smola, A., Huang, J., Schmittfull, M., Borgwardt, K., and Schölkopf, B. (2009) · 2009
Cited alongside, same era.
Causality
Pearl, J. (2009) · 2009
Cited alongside, same era.
A theory of learning from different domains
Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., and Vaughan, J. W. (2010) · 2010
Cited alongside, same era.
Impossibility theorems for domain adaptation
David, S. B., Lu, T., Luu, T., and Pál, D. (2010) · 2010
Cited alongside, same era.
On the hardness of domain adaptation and the utility of unlabeled target samples
Ben-David, S. and Urner, R. (2012) · 2012
Cited alongside, same era.
Domain generalization via invariant feature representation
Muandet, K., Balduzzi, D., and Schölkopf, B. (2013) · 2013
Cited alongside, same era.
Domain-adversarial neural networks
Original
Ajakan, H., Germain, P., Larochelle, H., Laviolette, F., and Marchand, M. (2014) · 2014
Cited alongside, same era.
Understanding machine learning: From theory to algorithms
Shalev-Shwartz, S. and Ben-David, S. (2014) · 2014
Cited alongside, same era.
Deeper, broader and artier domain generalization
Li, D., Yang, Y., Song, Y.-Z., and Hospedales, T. M. (2017) · 2017
Cited alongside, same era.
Learning non-discriminatory predictors
Original
Woodworth, B., Gunasekar, S., Ohannessian, M. I., and Srebro, N. (2017) · 2017
Cited alongside, same era.

Then

A reductions approach to fair classification
Original
Agarwal, A., Beygelzimer, A., Dudík, M., Langford, J., and Wallach, H. (2018) · 2018
Later among the works it cites.
Recognition in terra incognita
Beery, S., Van Horn, G., and Perona, P. (2018) · 2018
Later among the works it cites.
Pac learning guarantees under covariate shift
Original
Pagnoni, A., Gramatovici, S., and Liu, S. (2018) · 2018
Later among the works it cites.
Advances in Domain Adaptation Theory
Redko, I., Morvant, E., Habrard, A., Sebban, M., and Bennani, Y. (2019) · 2019
Later among the works it cites.
Invariant risk minimization game
Ahuja, K., Shanmugam, K., Varshney, K., and Dhurandhar, A. (2020) · 2020
Closest in time.
Invariant rationalization
Chang, S., Zhang, Y., Yu, M., and Jaakkola, T. S. (2020) · 2020
Closest in time.
Ai for radiographic covid-19 detection selects shortcuts over signal
DeGrave, A. J., Janizek, J. D., and Lee, S.-I. (2020) · 2020
Closest in time.
Domain generalization using a mixture of multiple latent domains
Matsuura, T. and Harada, T. (2020) · 2020
Closest in time.
Efficient domain generalization via common-specific low-rank decomposition
Piratla, V., Netrapalli, P., and Sarawagi, S. (2020) · 2020
Closest in time.
How neural networks extrapolate: From feedforward to graph neural networks
Xu, K., Zhang, M., Li, J., Du, S. S., Kawarabayashi, K.-I., and Jegelka, S. (2021) · 2021
Closest in time.

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…