Sharp Minimax Regret for Infinite-Memory Logistic Prediction

Abstract: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.

Information Theory (cs.IT); Machine Learning (cs.LG)

arXiv:2608.26515 [cs.IT]

(or arXiv:2608.26515v1 [cs.IT] for this version)

https://doi.org/10.48550/arXiv.2608.26515 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.