Search papers, labs, and topics across Lattice.
This paper investigates online prediction in a finite-alphabet context with infinite input memory, focusing on the role of lagged inputs in determining cumulative regret. By establishing a minimax cumulative-regret scale through a localized Bayesian mixture and a Toeplitz-design converse, the authors reveal that the regret can be tightly bounded for specific decay rates of the lagged inputs. Key findings indicate that the regret scales as $\Theta(\alpha^{-1}\log^2T)$ for exponential decay and $\Theta(T^{1/(2s)})$ for polynomial decay, highlighting the significant impact of input memory on prediction performance.
The minimax cumulative-regret scale reveals that even minor adjustments in input memory can lead to vastly different prediction outcomes.
We study online prediction for a specific finite-alphabet, exogenously driven source with infinite input memory. Independent Rademacher inputs $(U_t)$ are observed sequentially, and the next binary mark has logit $\sum_{j=1}^{t}\theta_jU_{t+1-j}$, where $\abs{\theta_j}\leq r_j$ and $\sum_jr_j\leq B$. Regret is expected cumulative excess log loss. Lag $j$ can affect prediction by scale $r_j$ and enters only $n_{T,j}=T-j+1$ prediction rounds, leading to the lag-resolved spectrum $\Gamma_T(r)=\sum_{j=1}^{T}\log\!\left(1+n_{T,j}r_j^2\right)$. For every summable envelope, a localized Bayesian mixture proves $\cR_T(r)\leq C\Gamma_T(r)$. For exponential and polynomial envelopes, under the stated finite-sample dimension condition, a Toeplitz-design converse proves $\cR_T(r)\geq c\Gamma_T(r)$, with constants allowed to depend on the fixed decay parameters and the logit bound. Thus $\Gamma_T(r)$ is the minimax cumulative-regret scale for this source class in these canonical regimes, giving $\Theta(\alpha^{-1}\log^2T)$ for $r_j=Ae^{-\alpha j}$ and $\Theta(T^{1/(2s)})$ for $r_j=Aj^{-s}$, $s>1$. The converse is specific to the exogenous lagged model and is not a profile-only theorem for arbitrary stationary infinite-memory sources. Retaining only the most recent $h$ inputs costs order $\sum_{j>h}n_{T,j}\theta_j^2$, yet the same worst-case truncation profile can correspond to polynomially different regret. A scaled online Newton predictor attains the spectrum upper bound.
