Generalization Bounds for Out-of-distribution Generalization

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) \textit{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.

Machine learning systems often perform well when tested on data similar to their training data, but their performance can drop when the test data come from a different environment, such as a new hospital, camera, population, or application setting. This problem is known as out-of-distribution generalization, and understanding its limits is important for building reliable machine learning systems. In this work, we study this problem from a theoretical perspective. We ask how much one can hope to learn from several training environments when the final testing environment may be different. We first establish lower bounds, which describe situations where no learning method can guarantee good performance without additional assumptions. We then prove upper bounds showing that, under certain structural conditions, a very simple method—training by minimizing the average error on the available source environments—can already achieve nearly the best possible statistical rate. This helps explain a surprising observation in prior empirical benchmarks: sophisticated out-of-distribution algorithms do not always outperform standard empirical risk minimization. Our results clarify both the limitations and the potential of out-of-distribution generalization, showing when success is theoretically impossible and when simple learning methods can be nearly optimal.