Beyond Discrepancy: A Closer Look at the Theory of Distribution Shift

Robi Bhattacharjee, Nicholas Rittler, Kamalika Chaudhuri
Proceedings of The 37th International Conference on Algorithmic Learning Theory, PMLR 313:1-19, 2026.

Abstract

Learning theory of distribution shift generally bounds performance on the target distribution as a function of the discrepancy between the source and target, rarely guaranteeing high target accuracy. Instead of relying on the discrepancy, we adopt an assumption inspired by Invariant Risk Minimization, where the source and target distributions are unified by an unknown feature projection. Under this assumption, we show that a learner can leverage the relationship between the source and target distributions to greatly reduce the number of required target samples to achieve high accuracy. To quantify this effect, we introduce a new combinatorial complexity measure—the distance dimension—and derive bounds for linear maps and neural networks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v313-bhattacharjee26a, title = {Beyond Discrepancy: A Closer Look at the Theory of Distribution Shift}, author = {Bhattacharjee, Robi and Rittler, Nicholas and Chaudhuri, Kamalika}, booktitle = {Proceedings of The 37th International Conference on Algorithmic Learning Theory}, pages = {1--19}, year = {2026}, editor = {Telgarsky, Matus and Ullman, Jonathan}, volume = {313}, series = {Proceedings of Machine Learning Research}, month = {23--26 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v313/main/assets/bhattacharjee26a/bhattacharjee26a.pdf}, url = {https://proceedings.mlr.press/v313/bhattacharjee26a.html}, abstract = {Learning theory of distribution shift generally bounds performance on the target distribution as a function of the discrepancy between the source and target, rarely guaranteeing high target accuracy. Instead of relying on the discrepancy, we adopt an assumption inspired by Invariant Risk Minimization, where the source and target distributions are unified by an unknown feature projection. Under this assumption, we show that a learner can leverage the relationship between the source and target distributions to greatly reduce the number of required target samples to achieve high accuracy. To quantify this effect, we introduce a new combinatorial complexity measure—the distance dimension—and derive bounds for linear maps and neural networks.} }
Endnote
%0 Conference Paper %T Beyond Discrepancy: A Closer Look at the Theory of Distribution Shift %A Robi Bhattacharjee %A Nicholas Rittler %A Kamalika Chaudhuri %B Proceedings of The 37th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Matus Telgarsky %E Jonathan Ullman %F pmlr-v313-bhattacharjee26a %I PMLR %P 1--19 %U https://proceedings.mlr.press/v313/bhattacharjee26a.html %V 313 %X Learning theory of distribution shift generally bounds performance on the target distribution as a function of the discrepancy between the source and target, rarely guaranteeing high target accuracy. Instead of relying on the discrepancy, we adopt an assumption inspired by Invariant Risk Minimization, where the source and target distributions are unified by an unknown feature projection. Under this assumption, we show that a learner can leverage the relationship between the source and target distributions to greatly reduce the number of required target samples to achieve high accuracy. To quantify this effect, we introduce a new combinatorial complexity measure—the distance dimension—and derive bounds for linear maps and neural networks.
APA
Bhattacharjee, R., Rittler, N. & Chaudhuri, K.. (2026). Beyond Discrepancy: A Closer Look at the Theory of Distribution Shift. Proceedings of The 37th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 313:1-19 Available from https://proceedings.mlr.press/v313/bhattacharjee26a.html.

Related Material