Fast Dynamic Regret with Logarithmic State for Online Least Squares

Online least squares in a non-stationary environment admits fast $T^{1/3}{P}_T^{2/3}$ dynamic regret under Euclidean comparator path length $P_T$. The continuous fixed-share implementation used for this rate keeps one Gaussian component for every possible start time, so its per-round cost grows with the horizon. We study which state is needed for the guarantee. The exact fixed-share posterior may require $t$ positive Gaussian components even on a scalar stream; we instead retain only the state used by the analysis. Our learner applies sleeping Gaussian exponential weights to dyadic interval lifetimes. It also builds a causal, lossy orthonormal representation of the feature stream under a summable budget $\epsilon$. The learner uses only the label bound, a reference point, and (for the lossy variant) $\epsilon$; it does not use $T$, $P_T$, the feature scale, or the comparator radius. The analysis combines an interval regret bound valid for every real parameter with an exact identity: weighted birth variation is the minimum weighted segment-start cost over all couplings with prescribed Gaussian marginals. This yields \widetilde{O}\\left( m_T + m_T^{2/3}T^{1/3}(P_T^{\mathrm{obs}})^{2/3} \right) with worst-case per-round time and space \widetilde{O}\\left(d(1+m_t)+(1+m_t^2)\log(t+1)\right). Here the retained dimension satisfies $m_T\le d$, so the dynamic term scales as $m_T^{2/3}$, and $P_T^{\mathrm{obs}}\le P_T$ is the shortest path preserving every comparator prediction. We also give a scalar lower bound matching the $T$- and $P_T$-exponents, a stream of feature rank $T$ whose gate retains one direction, an instance showing that the representation cross-term is unavoidable, and numerical checks of the reference implementation.