# Optimal Algorithms in Linear Regression under Covariate Shift: On the Importance of Precondition

arXiv: https://arxiv.org/abs/2502.09047 · HTML: https://mlsanity.com/paper/2502.09047/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2025.

## Built on by (most cited first, 5 of 5)

- [AdaPM: a Partial Momentum Algorithm for LLM Training](https://mlsanity.com/paper/2510.09103/) (2025)
- [How Does Preconditioning Guide Feature Learning in Deep Neural Networks?](https://mlsanity.com/paper/2509.25637/) (2025)
- [Accelerating Single-Pass SGD for Generalized Linear Prediction](https://mlsanity.com/paper/2603.01951/) (2026)
- [Learning with Synthetic Data via SGD in High-Dimensional Linear Regression](https://mlsanity.com/paper/2609.09572/) (2026)
- [Feature Normalization under Finite Training Budgets](https://mlsanity.com/paper/2610.16845/) (2026)

## Abstract (arXiv)

A common pursuit in modern statistical learning is to attain satisfactory generalization out of the source data distribution (OOD). In theory, the challenge remains unsolved even under the canonical setting of covariate shift for the linear model. This paper studies the foundational (high-dimensional) linear regression where the ground truth variables are confined to an ellipse-shape constraint and addresses two fundamental questions in this regime: (i) given the target covariate matrix, what is the min-max optimal algorithm under covariate shift? (ii) for what kinds of target classes, the commonly-used SGD-type algorithms achieve optimality? Our analysis starts with establishing a tight lower generalization bound via a Bayesian Cramer-Rao inequality. For (i), we prove that the optimal estimator can be simply a certain linear transformation of the best estimator for the source distribution. Given the source and target matrices, we show that the transformation can be efficiently computed via a convex program. The min-max optimal analysis for SGD leverages the idea that we recognize both the accumulated updates of the applied algorithms and the ideal transformation as preconditions on the learning variables. We provide sufficient conditions when SGD with its acceleration variants attain optimality.