Drift-Aligned Median-of-Means for Normalizing Non-Stationary Time Series

Deep time-series forecasters handle drifting data with a simple trick. They rescale each input window to zero mean and unit variance, forecast in that normalized space, and then undo the rescaling using the window's own mean and standard deviation. This recipe is known as reversible instance normalization. Its final forecast is essentially "normalized prediction × window standard deviation + window mean," so any error in those two numbers passes straight into every forecasted value. Sample means and standard deviations are the estimators most easily broken by a single spike: under heavy-tailed noise, their chance of a large error shrinks only polynomially in the failure probability. Robust statistics has a classical fix, median-of-means (split the data into blocks, average each block, take the median of the block averages). It gains logarithmic confidence scaling: pushing the failure probability from $10^{-2}$ down to $10^{-6}$ costs only a few more blocks. But median-of-means assumes every block estimates the same quantity, and this is exactly what fails when a series drifts. Consecutive blocks of a trending window have different means.

We propose an estimator that restores this "same target" assumption under drift. The window is cut into short contiguous chunks, and the chunks are dealt round-robin into $k$ blocks, so every block spans the whole window. Each block fits a local linear trend to its own chunks and reports the fitted level (and residual scale) at one shared reference time, such as the forecast origin. Every block now estimates the same number, the current level, and taking the median across blocks recovers exponential concentration. We plug this estimator in wherever RevIN, Non-stationary Transformers, or Dish-TS use window statistics. We then test the claim that matters for safety-critical forecasting. The claim is about the tail of the per-window error distribution, not only the average error, and it says that tail should grow like $\log(1/\delta)$ rather than like a power of $1/\delta$.

Core Claim

Existing stationarization wrappers are judged on average error and use plain sample statistics. RevIN normalizes with the window mean and standard deviation. Non-stationary Transformers feed the same raw statistics through a small network to rescale attention. Dish-TS learns separate level and scale coefficients for the lookback and the horizon. APT explicitly observes that these local statistics become unreliable under noise, missing values, and sharp local shifts. It responds by conditioning on timestamps rather than by making the statistics themselves robust.

On the robust-estimation side, generalized median-of-means and its metric-space extension, the Fréchet median of estimators, prove exponential concentration with $k \propto \log(1/\delta)$ blocks. Both assume the blocks are independent draws from a common distribution. These papers supply our method, and they also mark the assumption we have to repair.

Our claim is that a drift-aligned, chunk-interleaved median-of-means gives a normalizer whose error, with probability $1-\delta$, obeys a bound of the form

$$|\hat{\mu}_{\text{DA}} - \mu_{t_0}| \;\le\; C\left(\frac{\log(1/\delta)}{L}\right)^{\frac{\epsilon}{1+\epsilon}} + B_{\text{curv}} + B_{\text{dep}}(m).$$

Here $\hat{\mu}_{\text{DA}}$ is the median over $k \approx 8\log(1/\delta)$ blocks of each block's trend-fit level evaluated at reference time $t_0$. The quantity $\mu_{t_0}$ is the true local level at $t_0$, and $L$ is the window length. The exponent comes from assuming the noise has only $1+\epsilon$ finite moments, which is the standard median-of-means rate under that condition. $B_{\text{curv}}$ is the bias left over when the drift is not locally linear, and $B_{\text{dep}}(m)$ is a dependence penalty that shrinks as the chunk length $m$ grows under a mixing assumption. The scale estimate follows the same construction applied to detrended residuals, which requires $2(1+\epsilon)$ finite moments.

The design trade-off is explicit. Contiguous blocks keep blocks nearly independent but give them different targets under drift. Pure strided blocks, one point per slot, align the targets but make neighboring blocks strongly correlated. Chunks of length $m$ sit between the two, and $m$ becomes the single knob. The number of blocks depends only on $\delta$, not on the unknown tail exponent. That is the practical reason we prefer medians to truncated means, whose thresholds require knowing the tail exponent, as the SOMM/SOTM analysis in Safe Online Convex Optimization with Heavy-Tailed Observation Noises makes clear.

Research Program

The work has three parts.

The first part is analysis. We will prove the bound above for a model with locally linear drift, a bounded second derivative, and stationary mixing noise with $1+\epsilon$ moments. We will show that contiguous median-of-means carries a bias proportional to drift slope times window length, and that this bias never vanishes as $k$ grows. We will also derive how the forecast error of a reversible wrapper inherits the normalizer's error through the denormalization step. That derivation turns a statement about the estimator into a tail statement about the forecast. We aim for these results but do not presuppose them. If the dependence term cannot be controlled at useful chunk lengths on real data, we will report that.

The second part is integration. The estimator replaces the sample statistics in three places. In RevIN it supplies both the normalizer and the denormalizer, evaluated at the forecast origin rather than at the window mean. In Non-stationary Transformers it supplies the raw statistics that feed the attention-rescaling factors. This addresses the concern that spikes pushed through that network produce extreme attention logits. In Dish-TS, the drift-aligned level and slope enter the horizon network as an input and a residual prior, while the network still learns the full horizon coefficients.

The third part is evaluation. The evaluation reports how the upper quantiles of per-window error grow as $\delta$ decreases, alongside average error.

Baselines

The do-nothing reference is each backbone trained on globally z-scored data with no instance normalization. RevIN shows this reference is weak: N-BEATS on ETTh2 at horizon 960 goes from 6.408 to 0.471 MSE when RevIN is added. The naive robust reference is plain RevIN with sample statistics, run with the same backbones, lookback lengths, seeds, and a shared hyperparameter budget.

The strongest existing method on distribution shift is Dish-TS. It reports an average improvement of over 10% relative to RevIN and gains of 28.6% (univariate) and 21.9% (multivariate) over backbones. IN-Flow reports average improvements of 28.3% on PatchTST and 21.3% on iTransformer, so it is the strongest nonlinear competitor. APT reports 4–40% gains on ETTh1/2 and Exchange. We found no result on Lacuna for any of these methods under a tail-quantile or conditional-value-at-risk metric, so we will measure those numbers ourselves. All methods get the same data splits, backbones, training epochs, and number of tuning trials.

"Beating" a method has two parts. The proposal must show a statistically significant reduction in the 99th and 99.9th percentile per-window MSE, and in the mean error of the worst 1% of windows (the conditional value-at-risk), across seeds. It must also match the method's average MSE to within about 2%. Tail-only gains with a clear loss in average error would count as a trade-off, not a win.

Four ablations isolate the key ingredients. Contiguous median-of-means (same $k$) and strided median-of-means without per-block trend fits isolate the drift alignment. A single trend fit on the full window with no median isolates the median. Varying chunk length $m$ exposes the dependence trade-off.

Why not just…?

Why not just normalize with the window median and median absolute deviation? This is the most serious threat to a naive version of the idea. It is why we did not propose "median-of-means inside RevIN" alone: a median/MAD normalizer is equally robust to isolated spikes and costs nothing. What it lacks is drift correction. On a trending window it reports the level at the window's middle, not at the forecast origin, so its bias grows with slope. We include median/MAD RevIN as a baseline and expect it to match us on flat, spiky series. We expect it to lose on Exchange and trending ETT segments, and in the synthetic sweep over drift slope. If it does not lose there, the drift-alignment contribution fails.

Why not just fit a robust trend (Theil–Sen or Huber regression) to the whole window? This is also a real competitor, since it is both robust and drift-aware. Our argument is that median-of-means gives a deviation bound with an explicit $\log(1/\delta)$ dependence, a tail exponent that need not be known, and a direct dependence knob. Robust regression gives none of these without extra tuning, and its behavior under autocorrelated heavy-tailed noise is less characterized. This is a prediction, not a result. We run both robust regressions as baselines, and a tie on empirical tails would narrow the contribution to the theoretical certificate.

Why not just learn the horizon statistics, as Dish-TS does? A learned horizon network can absorb drift, but it is trained on average squared error from the same sample statistics. When a spike corrupts its inputs, it has no mechanism to discount them. We keep Dish-TS intact and compare it with and without the drift-aligned input, which directly tests whether robustness adds to learning.

Why not just train with gradient clipping or a Huber loss? Gorbunov et al. show that clipping yields logarithmic confidence scaling for optimization under heavy-tailed gradients. That result concerns the training trajectory on a fixed distribution. A clean training run can still produce catastrophic test forecasts, because corruption enters at test time through the denormalization step. We run clipped training as a baseline, and also combine it with our method, to separate the two effects.

Proposed Experiments

The decisive experiment is synthetic, because only there is the true level known. We generate series with linear and slowly curving trends, Student-t noise across a range of degrees of freedom, autocorrelation, injected spikes, and abrupt regime shifts in the style of the controlled-shift tests in IN-Flow. We then plot the empirical $(1-\delta)$ quantile of normalizer error against $\log(1/\delta)$ for sample, median/MAD, contiguous median-of-means, robust-regression, and drift-aligned estimators. The prediction has three parts. First, the sample mean's quantile curve should bend upward polynomially as the tails get heavier. Second, contiguous median-of-means should flatten in $\delta$ but rise with drift slope. Third, only the drift-aligned estimator should stay roughly linear in $\log(1/\delta)$ across slopes, up to a curvature bias that appears when the trend bends.

On real data we use ETTh1, ETTh2, Exchange, ECL, Weather, and ILI, with ILI chosen for its heavy-tailed outbreak surges. The backbones are Informer, N-BEATS, PatchTST, and iTransformer, at the standard horizons. We report average MSE and MAE, per-window error quantiles, and the worst-1% conditional value-at-risk. The number of test windows limits how small $\delta$ can be measured empirically, roughly $10^{-3}$ on ETT-sized splits, and we will not claim empirical tails beyond that. The theory is what extends the claim to smaller $\delta$.

A second decisive check injects synthetic spikes into clean ETT test windows at controlled rates. It measures how forecast error degrades for each normalizer, and in the Non-stationary Transformer it tracks the spread of the attention-rescaling factors. The drift-aligned normalizer should keep both flat, while sample statistics should not.

Any of three outcomes would weaken or falsify the proposal. The first is if median/MAD or Theil–Sen normalization matches us on trending data. The second is if the tails improve only at the cost of average accuracy. The third is if the chunk length needed to control dependence on real series leaves too few blocks to reach useful $\delta$.