mlsanityData to 14 Oct 2026

The Implicit Bias of Heterogeneity towards Invariance: A Study of Multi-Environment Matrix Sensing

arXiv 2403.01420 ↗First posted 3 Mar 2024cs.LG math.OCcited by 2

Not on the map. Why?

Abstract (arXiv)

Models are expected to engage in invariance learning, which involves distinguishing the core relations that remain consistent across varying environments to ensure the predictions are safe, robust and fair. While existing works consider specific algorithms to realize invariance learning, we show that model has the potential to learn invariance through standard training procedures. In other words, this paper studies the implicit bias of Stochastic Gradient Descent (SGD) over heterogeneous data and shows that the implicit bias drives the model learning towards an invariant solution. We call the phenomenon the implicit invariance learning. Specifically, we theoretically investigate the multi-environment low-rank matrix sensing problem where in each environment, the signal comprises (i) a lower-rank invariant part shared across all environments; and (ii) a significantly varying environment-dependent spurious component. The key insight is, through simply employing the large step size large-batch SGD sequentially in each environment without any explicit regularization, the oscillation caused by heterogeneity can provably prevent model learning spurious signals. The model reaches the invariant solution after certain iterations. In contrast, model learned using pooled SGD over all data would simultaneously learn both the invariant and spurious signals. Overall, we unveil another implicit bias that is a result of the symbiosis between the heterogeneity of data and modern algorithms, which is, to the best of our knowledge, first in the literature.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 37 of its 53 references that are in the map. First posted on arXiv 3 Mar 2024.

Builds on

37 of 53 references.

References · 37

  1. 2023GPT-4 Technical Reportcited by 18,396
  2. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  3. 2019Advances and Open Problems in Federated Learningcited by 3,046
  4. 2019Invariant Risk Minimizationcited by 1,854
  5. 2020Ditto: Fair and Robust Federated Learning Through Personalizationcited by 672
  6. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 655
  7. 2015Causal inference using invariant prediction: identification and confidence intervalscited by 536
  8. 2021Gradient Descent on Neural Networks Typically Occurs at the Edge of Stabilitycited by 427
  9. 2017Implicit Regularization in Matrix Factorizationcited by 322
  10. 2020The Risks of Invariant Risk Minimizationcited by 262
  11. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  12. 2019SGD on Neural Networks Learns Functions of Increasing Complexitycited by 204
25 more
  1. 2018Gradient descent aligns the layers of deep linear networkscited by 182
  2. 2020Directional convergence and alignment in deep learningcited by 178
  3. 2021Simple data balancing achieves competitive worst-group-accuracycited by 178
  4. 2019Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like processcited by 123
  5. 2021Label Noise SGD Provably Prefers Flat Global Minimizerscited by 121
  6. 2021Does Invariant Risk Minimization Capture Invariance?cited by 116
  7. 2018Convergence of Gradient Descent on Separable Datacited by 110
  8. 2021What Happens after SGD Reaches Zero Loss? --A Mathematical Frameworkcited by 107
  9. 2020Invariant Causal Prediction for Block MDPscited by 105
  10. 2020Shape Matters: Understanding the Implicit Bias of the Noise Covariancecited by 88
  11. 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
  12. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 78
  13. 2019The Implicit Bias of Depth: How Incremental Learning Drives Generalizationcited by 64
  14. 2022ZIN: When and How to Learn Invariance Without Environment Partition?cited by 58
  15. 2023Understanding Causality with Large Language Models: Feasibility and Opportunitiescited by 53
  16. 2021Nonlinear Invariant Risk Minimization: A Causal Approachcited by 42
  17. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 42
  18. 2023(S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stabilitycited by 36
  19. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  20. 2017Learning Causal Structures Using Regression Invariancecited by 32
  21. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  22. 2022Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrisationcited by 29
  23. 2023Environment Invariant Linear Least Squarescited by 17
  24. 2020Understanding Implicit Regularization in Over-Parameterized Single Index Modelcited by 12
  25. 2019On the Upload versus Download Cost for Secure and Private Matrix Multiplicationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Escaping Local Minima Provably in Non-convex Matrix Sensing: A Deterministic Framework via Simulated Liftingcited by 3
  2. 2026Towards Understanding Momentum Acceleration in River-Valley Loss Landscapecited by 1