Monotonic Risk Relationships under Distribution Shifts for Regularized Risk Minimization

Daniel LeJeune, Jiayu Liu, Reinhard Heckel

Abstract

Machine learning systems are often applied to data drawn from a different distribution than the training distribution. Recent work has shown that for a variety of classification and signal reconstruction problems, out-of-distribution (OOD) performance is strongly linearly correlated with in-distribution (ID) performance. This paper studies conditions under which a monotonic relationship between the performances of a model on two distributions is expected. We prove an exact asymptotic linear relation for squared error and a monotonic relation for misclassification error for ridge-regularized general linear models under covariate shift, as well as an approximate linear relation for linear inverse problems.

Introduction: The "Accuracy on the Line" Phenomenon

In real-world applications, machine learning models frequently encounter distribution shift, where production data differs from training data. Despite this, empirical studies have observed a striking trend: when plotting OOD accuracy against ID accuracy for various models, the results often form a straight line. This "Accuracy on the Line" phenomenon suggests that ID performance can serve as a reliable proxy for OOD reliability. This paper provides a rigorous mathematical foundation for these observations, explaining why and when these linear or monotonic relationships occur in regularized risk minimization.

Empirical evidence of the linear relationship between in-distribution (COCO 2017) and out-of-distribution (VOC 2012) mean squared error (MSE) across various object detection architectures.

Theoretical Framework

The authors utilize high-dimensional asymptotic analysis, examining model behavior as the number of features ($d$) and training samples ($n$) grow to infinity at a fixed ratio ($d/n$). The study focuses on Ridge-Regularized General Linear Models (GLMs), which minimize a loss function (e.g., squared error) alongside a squared penalty on weights.

A central component of the theory is the Subspace Model, which characterizes distribution shift as a change in the underlying feature subspace. The interaction between the shift and the ground-truth signal is quantified by parameters ($\gamma, \kappa, \mu$), determining if a shift makes a task inherently easier or harder based on how it aligns with the signal.

Key Insights and Mechanisms

The research reveals that linear and monotonic relationships are not accidental but are driven by specific mathematical properties:

  • Regression Linearity: For regression tasks, OOD risk is proven to be an affine function ($y = ax + b$) of ID risk, provided feature subspaces are well-aligned or the signal is learnable within the training subspace.
  • Classification Monotonicity: In classification, the relationship is strictly monotonic. The authors demonstrate that a linear relationship emerges after applying a specific transformation ($sec^2(\pi R)$), which mirrors the Probit/Logit transformations used in previous empirical work.
  • Independent Drivers: Interestingly, the linear relationships in regression and classification arise from different mechanisms: shifts in the feature subspace for regression versus shifts in feature scaling for classification.
  • Robustness of Ridge Regularization: The paper notes that while Ridge regression maintains these relationships robustly, other losses like Hinge or Logistic loss can break monotonicity if regularization is not precisely tuned.

Empirical Validation

The theoretical findings are validated across synthetic data and real-world benchmarks. In object detection experiments using COCO 2017 and VOC 2012, models like YOLOv5 and Faster R-CNN exhibit the predicted linear MSE correlation. In digit classification (MNIST to ARDIS), the theory accurately predicts performance "dips" across diverse architectures like AlexNet and ResNet.

Comprehensive analysis showing (left) the linear MSE fit for object detection, (center) the singular value spectra of the datasets, and (right) the subspace similarity k, which underpins the theoretical derivation.

Conclusion

This work provides a theoretical bridge between empirical observations of OOD performance and the underlying geometry of distribution shifts. While the results are most elegant for ridge regularization and covariate shifts, they offer a powerful tool for predicting model reliability in changing environments. Future research may extend these findings to label shifts or more complex semantic transformations that aren't easily captured by subspace alignment.

Summary updated

Abstract

Machine learning systems are often applied to data that is drawn from a different distribution than the training distribution. Recent work has shown that for a variety of classification and signal reconstruction problems, the out-of-distribution performance is strongly linearly correlated with the in-distribution performance. If this relationship or more generally a monotonic one holds, it has important consequences. For example, it allows to optimize performance on one distribution as a proxy for performance on the other. In this paper, we study conditions under which a monotonic relationship between the performances of a model on two distributions is expected. We prove an exact asymptotic linear relation for squared error and a monotonic relation for misclassification error for ridge-regularized general linear models under covariate shift, as well as an approximate linear relation for linear inverse problems.
BibTeX
@article{lejeune2024monotonic,
  author = {Daniel LeJeune and Jiayu Liu and Reinhard Heckel},
  title = {{Monotonic Risk Relationships under Distribution Shifts for Regularized Risk Minimization}},
  journal = {J. Mach. Learn. Res.},
  year = {2024},
}
Figure