Sharp Minimax Regret for Infinite-Memory Logistic Prediction

We determine the minimax cumulative log-loss regret of a finite-alphabet, exogenously driven source with genuinely infinite input memory: independent Rademacher inputs (Ut) are observed sequentially and the next binary mark has logit sumj≥1θjUt+1-j, the unknown coefficients obeying a summable envelope |θj|≤ rj, sumjrj≤ B. At horizon T, lag j can move the logit by at most rj and is exercised in only nT,j=(T-j+1)_+ rounds, and the two limitations combine into the sum GammaT(r)=sumj≤ Tlog(1+nT,jrj2). One coordinate-localised Bayesian mixture achieves RT(r)≤ CGammaT(r) for 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 GammaT(r) is the minimax regret scale here, giving Theta(α-1log2T) for rj=Ae-α j and Theta(T1/(2s)) for rj=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 OB(GammaT(r)) in polynomial time per round.