Online Nonstochastic Prediction: Logarithmic Regret via Predictive Online Least Squares

Motivated by the challenge of stabilizing a general unknown linear dynamical system (LDS) from observations, we study the natural prerequisite of online prediction. Our goal is to achieve sublinear regret with a memory footprint that adapts to the intrinsic complexity of the dynamics rather than the full hidden-state dimension. We focus on the practically central regime of systems with low instability complexity -- eigenvalues outside the real stable interval that do not decay rapidly, together with non-semisimple modes -- potentially embedded in an otherwise stable real spectrum of much higher dimension; we write $k$ for this count. This regime is the primary setting in which stabilization is plausible: we show that many systems with high instability complexity cannot be stabilized without exponentially large controls. Thus, prediction is meaningful for stabilization precisely when the instability complexity is small. Within this regime, we introduce a unified online algorithm that handles every LDS (including non-diagonalizable systems with complex or exploding modes) with a learnable parameter count of $\widetilde{O}(k)$. Finally, we prove a lower bound showing that $k$ is a valid complexity measure: any filter-based predictor needs at least $k$ filters. Experiments corroborate our theory: on a high-dimensional system, our predictor sharply outperforms prior methods at an equal parameter budget.

We study online prediction under distribution shift, where inputs arrive chronologically and outcomes are revealed only after prediction. In this setting, predictors must remain stable in quiet regimes yet adapt when regimes shift, and the right adaptation memory is unknown in advance. We propose MELO (Memory-hedged Exponentially Weighted Least-Squares Online aggregation), a model-agnostic method that hedges across adaptation scales: it wraps any non-anticipating base-predictor pool with exponentially weighted least-squares (EWLS) adaptation experts at multiple forgetting factors, and aggregates raw and EWLS-adapted forecasts with MLpol, a parameter-free online aggregation rule. Under boundedness conditions, we establish deterministic oracle inequalities showing that it competes with both the best raw predictor and the best bounded, time-varying affine combinations of the base predictions, up to a path-length-dependent tracking cost and a sublinear aggregation overhead. We evaluate MELO on French national electricity-load forecasting through the COVID-19 lockdown using no regime indicators, lockdown dates, or policy covariates. MELO reduces overall RMSE by 34.7% relative to base-only MLpol and achieves lower overall RMSE than a TabICL reference supplied with an external COVID policy-response covariate. Moreover, MELO requires only lightweight per-step recursive updates without model retraining.

We determine the minimax cumulative log-loss regret of a finite-alphabet, exogenously driven source with genuinely infinite input memory: independent Rademacher inputs $(U_t)$ are observed sequentially and the next binary mark has logit $\sum_{j\ge1}θ_jU_{t+1-j}$, the unknown coefficients obeying a summable envelope $|θ_j|\le r_j$, $\sum_jr_j\le B$. At horizon $T$, lag $j$ can move the logit by at most $r_j$ and is exercised in only $n_{T,j}=(T-j+1)_+$ rounds, and the two limitations combine into the sum $Γ_T(r)=\sum_{j\le T}\log(1+n_{T,j}r_j^{2})$. One coordinate-localised Bayesian mixture achieves $R_T(r)\le CΓ_T(r)$ for \emph{every} summable envelope with $C$ universal. Our main result is a matching nonasymptotic converse for the canonical exponential and polynomial envelopes; its new ingredients are a modular finite-sample information bound for logistic experiments with an exogenous random design, and a conditioning estimate for the overlapping Toeplitz lag matrix obtained by exhibiting each off-diagonal Gram sum as a sum of independent Rademacher variables indexed by the edges of a forest, needing neither local asymptotic normality nor any spectral theorem for random Toeplitz matrices. So $Γ_T(r)$ is the minimax regret scale here, giving $Θ(α^{-1}\log^{2}T)$ for $r_j=Ae^{-αj}$ and $Θ(T^{1/(2s)})$ for $r_j=Aj^{-s}$, $s>1$ --- the latter without the extra $(\log T)^{1-1/(2s)}$ factor any window-truncation analysis pays. We also show memory decay cannot determine regret, and that a profile-scaled online Newton predictor attains $O_B(Γ_T(r))$ in polynomial time per round.