Invariant Subspace Decomposition

Margherita Lazzaretto, Jonas Peters, Niklas Pfister

Introduction

Predicting the future is inherently difficult when the underlying rules of a system evolve over time. In machine learning, the standard assumption of stationarity—that the relationship between inputs ($X$) and targets ($Y$) remains constant—is frequently violated in domains ranging from finance to physical sensing. When such "distribution shifts" occur, practitioners face a difficult trade-off: rely on a large but potentially "stale" historical dataset, or adapt using a small, high-variance sample of recent data.

Invariant Subspace Decomposition (ISD), proposed by Lazzaretto, Peters, and Pfister, offers a novel framework to navigate this trade-off. By decomposing the predictor space into stable and time-varying components, ISD enables high-precision adaptation even with minimal new data.

Problem Formulation

Most regression models struggle with non-stationarity. If the relationship between $X$ and $Y$ changes at time $t$, a model trained on historical data from $t-n$ will be biased. Conversely, a "rolling window" Ordinary Least Squares (OLS) model trained only on the most recent $m$ observations often suffers from excessive variance due to the small sample size.

Existing approaches, such as "maximin" effects, seek a single model that performs robustly across all past environments. However, these are often overly conservative. ISD addresses this by explicitly modeling the change in coefficients $\gamma_{0,t}$ over time: $$Y_t = X_t^\top \gamma_{0,t} + \epsilon_t$$ The goal is to exploit massive historical datasets to improve predictions at a specific test point $t^*$ where the system has shifted.

The ISD Framework

The core innovation of ISD is the decomposition of the predictor space into an invariant subspace ($\mathcal{S}^{inv}$), where the relationship with the target is constant, and a residual subspace ($\mathcal{S}^{res}$), where it varies.

Comparison of OLS and ISD estimation. ISD identifies invariant and residual subspaces to reduce adaptation variance.

The methodology follows three primary steps:

  1. Joint Block Diagonalization: The framework utilizes covariance matrices from different historical time windows to find a basis that simultaneously block-diagonalizes them, identifying independent groups of predictors.
  2. Identifying Invariance: The algorithm determines which groups maintain a stable relationship with $Y$ across the entire history. These constitute $\mathcal{S}^{inv}$, while the remainder form $\mathcal{S}^{res}$.
  3. Two-Step Estimation:
  4. Invariant Component ($\beta^{inv}$): Estimated using the entirety of historical data. Since this relationship is stable, more data directly translates to higher precision.
  5. Residual Component ($\delta^{res}_t$): Estimated using a small "adaptation window" of recent data. Because the dimensionality of the residual subspace is typically much lower than the full feature space, the model requires far fewer samples to adapt than a standard OLS model.

Experimental Results

The authors validated ISD using both simulated data and a real-world physical system known as the "Light Tunnel." In the Light Tunnel experiment, the relationship between RGB light sources and sensors shifts as polarizers rotate, while internal LED relationships remain invariant.

Performance comparison on historical and adaptation data. ISD shows significantly lower cumulative variance compared to standard OLS and zero-shot estimators.

Key findings include:

  • Sample Efficiency: ISD achieves low error levels with an adaptation window of only $1.5 \times p$ observations, whereas standard OLS requires significantly more data to stabilize.
  • Zero-Shot Generalization: Even without adaptation data, the invariant component $\beta^{inv}$ provides meaningful predictions that often outperform global OLS and robust "maximin" estimators.
  • Theoretical Guarantees: The authors provide finite-sample bounds showing that ISD's error is proportional to $dim(\mathcal{S}^{inv})/n + dim(\mathcal{S}^{res})/m$. This ensures that as long as a stable subspace exists, ISD will outperform standard OLS.

Conclusion

Invariant Subspace Decomposition bridges the gap between signal processing and statistics to solve the challenge of non-stationarity. By isolating invariant features, it reduces the "re-learning" burden during distribution shifts. While currently limited to linear models, the framework provides a robust foundation for future extensions into non-linear manifolds and applications in online learning or contextual bandits.

Summary updated

Abstract

We consider the task of predicting a response Y from a set of covariates X in settings where the conditional distribution of Y given X changes over time. For this to be feasible, assumptions on how the conditional distribution changes over time are required. Existing approaches assume, for example, that changes occur smoothly over time so that short-term prediction using only the recent past becomes feasible. In this work, we propose a novel invariance-based framework for linear conditionals, called Invariant Subspace Decomposition (ISD), that splits the conditional distribution into a time-invariant and a residual time-dependent component. As we show, this decomposition can be utilized both for zero-shot and time-adaptation prediction tasks, that is, settings where either no or a small amount of training data is available at the time points we want to predict Y at, respectively. We propose a practical estimation procedure, which automatically infers the decomposition using tools from approximate joint matrix diagonalization. Furthermore, we provide finite sample guarantees for the proposed estimator and demonstrate empirically that it indeed improves on approaches that do not use the additional invariant structure.
BibTeX
@misc{lazzaretto2024invariant,
  author = {Margherita Lazzaretto and Jonas Peters and Niklas Pfister},
  title = {{Invariant Subspace Decomposition}},
  year = {2024},
  eprint = {2404.09962},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2404.09962},
}
Figure