Sharp Minimax Regret for Infinite-Memory Logistic Prediction

arXiv:2608.26515v1 Announce Type: cross 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}heta_jU_{t+1-j}, where abs{heta_j}leq r_j and sum_jr_jleq 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^2right). For every summable envelope, a localized Bayesian mixture proves R_T(r)leq CGamma_T(r). For exponential and polynomial envelopes, under the stated finite-sample dimension condition, a Toeplitz-design converse proves R_T(r)geq cGamma_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}heta_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.

Related

• Online Inference in Distributional Temporal-Difference Learning
• Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling
• When Similarity Is Interaction-Driven: Quantum Kernels for Regime-Sensitive Learning
• Sharp Root Anti-Concentration via Projective Incidence and Ordered Root Laws

Source: arXiv cs.LG | 2026-08-28