Generalization Bounds for Out-of-distribution Generalization

Xin Zou, Xiuwen Gong, Weiwei Liu
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:168695-168719, 2026.

Abstract

Out-of-distribution (OOD) generalization has attracted increasing research attention in recent years, owing to its promising empirical results in real-world applications. However, theoretical studies on OOD generalization remain limited, particularly with respect to lower bounds on the generalization error. To better understand how source data contributes to improved OOD generalization performance, we take an initial step toward establishing a lower bound on the OOD generalization error, and subsequently investigate upper bounds from the perspective of statistical learning theory. Interestingly, we find that under the RCS and empirical-RCS conditions, simply minimizing the average empirical risk over the source domains can yield a nearly optimal error rate (up to a logarithmic factor) without requiring knowledge or estimation of distributional parameters or the discrepancy between source and target domains. This conditional result provides a theoretical perspective on the surprising phenomenon observed in DomainBed, where carefully designed OOD generalization algorithms fail to outperform the simple empirical risk minimization (ERM) algorithm. Our results also imply a no-free-lunch theorem and provide an optimistic bound for OOD generalization.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-zou26f, title = {Generalization Bounds for Out-of-distribution Generalization}, author = {Zou, Xin and Gong, Xiuwen and Liu, Weiwei}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {168695--168719}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/zou26f/zou26f.pdf}, url = {https://proceedings.mlr.press/v306/zou26f.html}, abstract = {Out-of-distribution (OOD) generalization has attracted increasing research attention in recent years, owing to its promising empirical results in real-world applications. However, theoretical studies on OOD generalization remain limited, particularly with respect to lower bounds on the generalization error. To better understand how source data contributes to improved OOD generalization performance, we take an initial step toward establishing a lower bound on the OOD generalization error, and subsequently investigate upper bounds from the perspective of statistical learning theory. Interestingly, we find that under the RCS and empirical-RCS conditions, simply minimizing the average empirical risk over the source domains can yield a nearly optimal error rate (up to a logarithmic factor) without requiring knowledge or estimation of distributional parameters or the discrepancy between source and target domains. This conditional result provides a theoretical perspective on the surprising phenomenon observed in DomainBed, where carefully designed OOD generalization algorithms fail to outperform the simple empirical risk minimization (ERM) algorithm. Our results also imply a no-free-lunch theorem and provide an optimistic bound for OOD generalization.} }
Endnote
%0 Conference Paper %T Generalization Bounds for Out-of-distribution Generalization %A Xin Zou %A Xiuwen Gong %A Weiwei Liu %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-zou26f %I PMLR %P 168695--168719 %U https://proceedings.mlr.press/v306/zou26f.html %V 306 %X Out-of-distribution (OOD) generalization has attracted increasing research attention in recent years, owing to its promising empirical results in real-world applications. However, theoretical studies on OOD generalization remain limited, particularly with respect to lower bounds on the generalization error. To better understand how source data contributes to improved OOD generalization performance, we take an initial step toward establishing a lower bound on the OOD generalization error, and subsequently investigate upper bounds from the perspective of statistical learning theory. Interestingly, we find that under the RCS and empirical-RCS conditions, simply minimizing the average empirical risk over the source domains can yield a nearly optimal error rate (up to a logarithmic factor) without requiring knowledge or estimation of distributional parameters or the discrepancy between source and target domains. This conditional result provides a theoretical perspective on the surprising phenomenon observed in DomainBed, where carefully designed OOD generalization algorithms fail to outperform the simple empirical risk minimization (ERM) algorithm. Our results also imply a no-free-lunch theorem and provide an optimistic bound for OOD generalization.
APA
Zou, X., Gong, X. & Liu, W.. (2026). Generalization Bounds for Out-of-distribution Generalization. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:168695-168719 Available from https://proceedings.mlr.press/v306/zou26f.html.

Related Material