PaperlayerView exact revision on arXiv

Source-linked AI summary

Invariant Risk Minimization Games

Kartik Ahuja, Karthikeyan Shanmugam, Kush R. Varshney, Amit Dhurandhar

arXiv:2002.04692v2cs.LGstat.ML

TL;DR

Spurious correlations make standard risk minimization brittle when test distributions differ from training distributions. The paper recasts invariant risk minimization as a Nash equilibrium problem for an ensemble game and solves it with best response dynamics. Its equilibria equal invariant predictors for finite environments, while experiments report comparable or better accuracy with lower variance than the related bi-level method.

  • Problem

    Standard risk minimization is brittle under distribution shifts caused by spurious correlations, motivating predictors that remain invariant across environments.

  • Method

    The paper assigns each environment a classifier component in an ensemble game and uses best response dynamics to seek its Nash equilibrium.

  • Results

    The game's Nash equilibria equal the invariant predictors across finite training environments, including a broad class of nonlinear classifiers and transformations.

  • Takeaways & Limitations

    The equivalence enables game-theoretic tools to find invariant predictors and preserves the related generalization result to a large set of unseen environments.

  • Takeaways & Limitations

    The related robust-optimization comparison assumes test distributions lie within the convex hull of training distributions, which is not true in many settings; the theoretical existence result also assumes affine closure.

Abstract

from arXiv · show

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. (2019). One key theoretical contribution is showing that the set of Nash equilibria for the proposed game are equivalent to the set of invariant predictors for any finite number of environments, even with nonlinear classifiers and transformations. As a result, our method also retains the generalization guarantees to a large set of environments shown in Arjovsky et al. (2019). The proposed algorithm adds to the collection of successful game-theoretic machine learning algorithms such as generative adversarial networks.

1 Introduction

The paper addresses brittle risk minimization under spurious correlations by reformulating invariant prediction as an ensemble game among environments. Best response dynamics provide a simple training procedure whose predictors match invariant predictors theoretically and perform competitively with lower variance empirically.

  • Motivation: Spurious correlations learned in training data can fail under distribution changes, such as associating green pastures with cows and deserts with camels.A CNN consequently misclassified cows photographed on sandy beaches.
  • Related approach: IRM seeks a representation whose optimal classifier is invariant across training environments, but its formulation creates a challenging bi-level optimization problem.The related formulation fixes a simple linear classifier and seeks an approximately locally optimal representation.
  • Proposed approach: Each environment controls one classifier component in an ensemble game, while all environments use the full ensemble to make predictions.An environment chooses its contribution to minimize its environment-specific risk.
  • Theory: The ensemble game's solution set equals the invariant predictors across training environments for a large class of nonlinear classifiers.This establishes the central theoretical equivalence of the proposed formulation.
  • Algorithm: Best response dynamics let environments take turns updating their classifiers toward lower environment-specific risk.The implementation is described as simple, and the method does not restrict classifiers to be linear.
  • Empirical findings: Across several datasets, the approach achieves better or comparable performance with much lower standard deviation than the related method.The comparison is against the formulation associated with [1].

2 Related Work

Related work addresses distribution shift through causal invariance, feature-selection principles, continuous representation learning, and distribution-matching or robust optimization methods. These approaches rely on different assumptions, including causal structure, conditional invariance, or test distributions lying within the convex hull of training sources.

  • Invariance principles in causality: Causal invariance principles identify non-spurious factors whose conditional relationship with the target remains invariant across interventions that do not affect the target mechanism.Under that condition, predictors based on causal factors are robust to unseen interventions.
  • Feature selection: Some methods use conditional independence tests and graph-theoretic tools to select invariant, maximally predictive feature subsets when causal Bayesian network structure is available.These approaches primarily select subsets of features rather than continuous transformations.
  • Continuous representations: IRM reformulates invariance as optimization over transformations in a continuous space, supporting settings such as computer vision where causal features may be latent.The related formulation uses an optimal classifier on the transformed representation.
  • Distribution shift methods: Sample weighting, domain adaptation, and robust optimization are alternative approaches to training-test distribution shift.Robust optimization considers worst-case loss over convex combinations of training sources.
  • Distribution shift methods: The convex-hull robust-optimization assumption is not true in many settings because test distributions may fall outside the convex hull of training distributions.This is the stated boundary of that approach.

3 Preliminaries

The preliminaries define normal-form games, predictors, risks, representations, and invariant predictors, then express IRM as a constrained optimization problem. They also define the corresponding solution sets and note their dependence on the chosen classifier and representation classes.

  • Game theory concepts: A normal-form game consists of players, strategy sets, and utility functions, with each player choosing an action from its strategy set.Finite games have finite strategy sets, while continuous games have uncountably infinite joint strategy spaces.
  • Game theory concepts: A pure-strategy Nash equilibrium is a strategy profile satisfying the equilibrium condition defined for unilateral deviations.The supplied passage introduces the concept but does not include the full displayed condition.
  • Invariant risk minimization: IRM defines a predictor f from inputs to real-valued scores and evaluates it using environment-specific risk based on a loss between predictions and labels.For multiclass classification, scores can be converted to hard labels by selecting the highest-scoring class.
  • Invariant risk minimization: A representation elicits an invariant predictor when one classifier achieves minimum risk across all environments after composing it with that representation.The classifier and representation belong to classes Hw and HΦ, respectively.
  • Invariant risk minimization: IRM can be written as a constrained optimization problem whose feasible pairs produce invariant predictors across the training environments.The resulting predictor is the composition w ◦ Φ.
  • Solution sets: SIV contains representation-classifier pairs satisfying IRM's constraints, while ˆSIV contains their corresponding composed invariant predictors.The notation distinguishes pairs from the predictors obtained by composition.
  • Solution sets: The sets of invariant solutions depend on the selected classifier class Hw and representation class HΦ.The paper suppresses this dependence in notation until later sections.
  • Setup: The IRM formulation applies to continuous and categorical data, with categorical features or labels one-hot encoded.This is an implementation detail of the setup.

4 Ensemble Invariant Risk Minimization Games

EIRM reformulates invariant risk minimization as an ensemble game in which environments choose classifiers, then characterizes Nash-equilibrium predictors and their relationship to invariant predictors.

  • 4.1 Game-Theoretic Reformulation: EIRM gives each environment its own classifier and averages these classifiers into an overall ensemble predictor.All environments use the same ensemble for prediction.
  • 4.1 Game-Theoretic Reformulation: The ensemble formulation automatically enforces invariance and lets environments choose classifiers from the full class H_w.Its constraints are equivalent to the pure Nash equilibria of the defined game.
  • 4.1 Game-Theoretic Reformulation: Each environment minimizes its own risk by changing its classifier while holding the other environments’ classifiers fixed.The resulting interaction is a game whose utilities are negative ensemble risk.
  • 4.2 Equivalence Between NE and Invariant Predictors: The section asks whether predictors obtained from EIRM Nash equilibria equal invariant predictors across the training environments.This equivalence is stated as the central relationship under study.
  • 4.2 Equivalence Between NE and Invariant Predictors: Affine closure permits the function class H_w to support finite sums and scalar multiplication, including nonlinear models such as ReLU networks.Other listed examples include kernel classifiers, ensembles, and functions in Lp space.
  • 4.2 Equivalence Between NE and Invariant Predictors: The equivalence holds for fixed representations, with the EIRM and invariant-predictor sets satisfying Ŝ_EIRM(Φ) = Ŝ_IV(Φ).The result applies under mild conditions and supports a stronger characterization developed through augmented tuples and decompositions.

X (I) and ˆSEIRM

The section characterizes when ensemble-game equilibria recover invariant predictors and presents best-response training procedures for finding them. It also gives generative and architectural conditions supporting equilibrium existence and invariant prediction.

  • Fixing the representation to identity is sufficient to recover all bounded-Lp invariant predictors obtainable through arbitrary representations.
  • When the data follow the stated causal generative model and Hw contains g, g is an invariant predictor and any decomposition of g is a pure Nash equilibrium under affine closure.
  • Under Assumption 4, a pure-strategy Nash equilibrium exists, and an interior equilibrium yields an invariant predictor among all linear models.
  • For broad model classes, pure Nash equilibria may not exist, whereas mixed equilibria are guaranteed under the stated relaxation.
  • Best-response dynamics update one environment’s classifier at a time to minimize its environment-specific risk, while the representation may remain fixed or be updated periodically.

5 Experiments

Experiments evaluate F-IRM and V-IRM across several datasets, comparing accuracy and variance with ERM, robust training, and IRM. The Colored Fashion MNIST analysis further examines training oscillations and their relationship to spurious color correlations.

  • Training procedure: Best response training alternates environments, each minimizing its respective objective, and can periodically update the representation learner.The implementation repeats environment updates until a training criterion is reached.
  • Colored MNIST: F-IRM achieves 59.9 ± 2.7 percent testing accuracy on Colored MNIST, compared with 62.75 ± 9.5 percent for IRM.F-IRM has comparable mean accuracy with much lower standard deviation.
  • Colored Fashion MNIST: 70.2 ± 1.5 percent is achieved by V-IRM on Colored Fashion MNIST, producing the best reported mean and standard deviation.
  • Colored Desprites: On Colored Desprites, V-IRM achieves 50.0 ± 0.2 percent, while IRM achieves 51.8 ± 6 percent.
  • Structured Noise Fashion MNIST: F-IRM achieves 62.0 ± 2.0 percent on Structured Noise Fashion MNIST, comparable with IRM at 63.9 ± 10.9 percent but with lower standard deviation.
  • Oscillation analysis: On Colored Fashion MNIST, ensemble training accuracy oscillates after initially increasing, consistent with known behavior of best response dynamics.The analysis uses accuracy and color-correlation plots to study these oscillations.
  • Oscillation analysis: The oscillation has a high-accuracy state at 88% with heavy negative color correlation and a lower-accuracy state at 75% with correlation close to zero.The figures track ensemble accuracy, ensemble-color correlation, and individual-model color correlations.
  • Oscillation analysis: Oscillations arise from alternating model updates: one model reduces color correlation while the other increases reliance on color, creating a continuing push-and-pull cycle.The environments differ in how many examples benefit from exploiting color as a spurious feature.

6 Conclusion

The paper introduces a game-theoretic framework for learning invariant predictors from multiple environments. Its ensemble-game solutions match invariant predictors, with comparable performance and lower variance than the existing framework.

  • The authors propose game-theoretic tools as a framework for learning invariant predictors from multiple environments.
  • The framework constructs an ensemble game in which each environment controls one portion of the classifier ensemble.
  • The set of solutions to the ensemble game is exactly the set of invariant predictors across training environments.
  • The framework performs comparably to the existing framework while exhibiting lower variance.

7 Appendix

The appendix develops theoretical results for equilibrium existence, affine-closed model classes, ReLU-network approximation, and recovery of invariant predictors in causal settings. It distinguishes pure from mixed equilibria and identifies conditions under which equilibria yield invariant predictors.

  • Affine closure is satisfied by linear classifiers, RKHS models, ensembles with arbitrary weak learners, Lp spaces, and ReLU networks with arbitrary depth.
  • ReLU networks can approximate relevant functions arbitrarily closely, and Lipschitz losses transfer function approximation into arbitrarily close risks.
  • When Φ = I, the EIRM game recovers an invariant predictor based on the causal parents of Y.
  • Under Assumption 4, a pure Nash equilibrium exists, and an interior equilibrium yields an invariant predictor among linear models.
  • For general model classes, relaxing deterministic classifiers to mixed strategies guarantees a Nash equilibrium.

7.3 Game Theory Concepts Continued

This section states standard equilibrium-existence results for continuous and mixed-strategy games. Compactness, convexity, continuity, and concavity support pure equilibria, while weaker conditions support mixed equilibria.

  • A pure-strategy Nash equilibrium exists when each action set is compact and convex, utilities are continuous, and each utility is concave in its own action.
  • Mixed strategies let each player choose a probability distribution over its action set rather than a deterministic action.
  • Every finite game has a mixed-strategy Nash equilibrium.
  • Under nonempty compact action sets and continuity of utilities, a mixed-strategy Nash equilibrium is guaranteed.

7.4 Deriving the expression for backpropagation

The appendix derives backpropagation expressions for the ensemble’s neural-network scores. It combines model scores, applies softmax probabilities, forms the log-likelihood, and differentiates with respect to each model’s score.

  • The ensemble combines the class-k scores produced by two neural networks before applying softmax.
  • Softmax converts the summed class scores into the overall probability for each class.
  • The log-likelihood is written for an input x with label y after converting y to a one-hot vector.
  • The appendix differentiates the log-likelihood with respect to each model’s score to obtain the backpropagation expression.

7.5 Computing Environment

The experiments ran on a 2.3 GHZ Intel Core i9 processor with 32 GB of 2400 MHz DDR4 memory.

  • The experiments used a 2.3 GHZ Intel Core i9 processor and 32 GB of memory at 2400 MHz DDR4.

7.6 Description of the Datasets

The experiments use modified MNIST digits, Fashion MNIST, and Desprites datasets with label noise and environment-specific spurious correlations. They evaluate fixed- and variable-representation game architectures alongside an IRM baseline under shared optimization settings.

  • Datasets: Colored MNIST digits classify whether digits are below or above 5, with noisy labels and color correlations that reverse in the test environment.Two training environments contain 30,000 points each, while the test environment contains 10,000 points; color-label flip probabilities are 0.2, 0.1, and 0.9.
  • Datasets: Colored Fashion MNIST classifies footwear versus clothing after adding color-based spurious correlations and 25% preliminary-label noise.The two training and one test environments use color-label flip probabilities of 0.2, 0.1, and 0.9.
  • Datasets: Colored Desprites classifies circles versus squares with noisy labels and environment-dependent color correlations.Preliminary labels assign circles to 0 and squares to 1; the color-label flip probabilities are 0.2, 0.1, and 0.9 across the environments.
  • Datasets: Structured-noise Fashion MNIST replaces color correlations with small squares placed in opposite image corners according to the labels.The added squares are 3×3 in the top-left and 2×2 in the bottom-right; the passage describes three environments but does not provide the remainder of their construction.
  • Architectures: The fixed-Φ game uses a two-hidden-layer multilayer perceptron, while the variable-Φ game separates a representation learner from the classifier.Across experiments, hidden layers use 390 units, ELU activations, L2 regularization of 1.25e-3, dropout of 0.75, and a two-unit output.
  • Optimization: Training uses Adam with learning rate 2.5e-4, cross-entropy loss, batch size 256, and a one-epoch warm start, with termination determining trial length.The IRM baseline uses the architecture described in its referenced implementation, including two 390-unit ReLU layers with L2 regularization of 1.1e-3.

7.7 Figures Continued

The continued figures report ensemble accuracy, inter-environment accuracy differences, and correlations with color across datasets and both game variants. They use ltr=1 for the main experiments, while extended V-IRM training on Desprites shows persistent stable oscillations and continued avoidance of spurious correlations.

  • Figure coverage: Figures 5–36 cover all datasets and both F-IRM and V-IRM games using the paper’s termination criteria and ltr=1 updates.Figures 2–4 instead use ltr=5 to make oscillations visually clearer; the reported figures reproduce the trends described in the experiments section.
  • Extended training: Extended V-IRM training on Colored Desprites produces stable, persistent oscillations rather than eliminating them.Figures 36–40 examine the same setting after many more training steps.
  • Figure coverage: The figure series compares ensemble accuracy, accuracy differences between environments, ensemble color correlation, and individual-model correlations.These comparisons are repeated for Colored Fashion MNIST, Colored Digits MNIST, Colored Desprites, and Structured Noise Fashion MNIST across F-IRM and V-IRM variants.
  • Extended training: The extended-training state continues to yield an ensemble that does not exploit spurious correlations.This observation is reported for V-IRM on the Desprites dataset after the oscillations persist.
  • Dataset-specific panels: The remaining figures apply the same accuracy and correlation comparisons to Colored Digits MNIST, Colored Desprites, and Structured Noise Fashion MNIST.Their captions identify the dataset, game variant, ensemble accuracy, inter-environment difference, and color-correlation comparison.
Loading 2002.04692v2…