Empirical or Invariant Risk Minimization? A Sample Complexity Perspective

• URL: http://arxiv.org/abs/2010.16412v2
• Date: Fri, 19 Aug 2022 17:20:03 GMT
• Title: Empirical or Invariant Risk Minimization? A Sample Complexity Perspective
• Authors: Kartik Ahuja, Jun Wang, Amit Dhurandhar, Karthikeyan Shanmugam, Kush R. Varshney
• Abstract summary: It is unclear when in-variant risk generalization (IRM) should be preferred over the widely-employed empirical risk minimization (ERM) framework. We find that depending on the type of data generation mechanism, the two approaches might have very different finite sample and behavior. We further investigate how different factors -- the number of environments, complexity of the model, and IRM penalty weight -- impact the sample complexity of IRM in relation to its distance from the OOD solutions.
• Score: 49.43806345820883
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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. For example, in the covariate shift setting we see that the two approaches not only arrive at the same asymptotic solution, but also have similar finite sample behavior with no clear winner. For other distribution shifts such as those involving confounders or anti-causal variables, however, the two approaches arrive at different asymptotic solutions where IRM is guaranteed to be close to the desired OOD solutions in the finite sample regime, while ERM is biased even asymptotically. We further investigate how different factors -- the number of environments, complexity of the model, and IRM penalty weight -- impact the sample complexity of IRM in relation to its distance from the OOD solutions

Related papers

• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Continual Invariant Risk Minimization [46.051656238770086]
  Empirical risk minimization can lead to poor generalization behavior on unseen environments if the learned model does not capture invariant feature representations. Invariant risk minimization (IRM) is a recent proposal for discovering environment-invariant representations.
  arXiv  Detail & Related papers  (2023-10-21T11:44:47Z)
• Empirical Risk Minimization with Relative Entropy Regularization [6.815730801645783]
  The empirical risk minimization (ERM) problem with relative entropy regularization (ERM-RER) is investigated. The solution to this problem, if it exists, is shown to be a unique probability measure, mutually absolutely continuous with the reference measure. For a fixed dataset and under a specific condition, the empirical risk is shown to be a sub-Gaussian random variable.
  arXiv  Detail & Related papers  (2022-11-12T09:41:02Z)
• Mitigating multiple descents: A model-agnostic framework for risk monotonization [84.6382406922369]
  We develop a general framework for risk monotonization based on cross-validation. We propose two data-driven methodologies, namely zero- and one-step, that are akin to bagging and boosting.
  arXiv  Detail & Related papers  (2022-05-25T17:41:40Z)
• The Risks of Invariant Risk Minimization [52.7137956951533]
  Invariant Risk Minimization is an objective based on the idea for learning deep, invariant features of data. We present the first analysis of classification under the IRM objective--as well as these recently proposed alternatives--under a fairly natural and general model. We show that IRM can fail catastrophically unless the test data are sufficiently similar to the training distribution--this is precisely the issue that it was intended to solve.
  arXiv  Detail & Related papers  (2020-10-12T14:54:32Z)
• An Empirical Study of Invariant Risk Minimization [5.412466703928342]
  Invariant risk minimization is a proposed framework for learning predictors that are invariant to spurious correlations. Despite its theoretical justifications, IRM has not been extensively tested across various settings. We empirically investigate several research questions using IRMv1, which is the first practical algorithm proposed to approximately solve IRM.
  arXiv  Detail & Related papers  (2020-04-10T12:23:29Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.