# Sharp Minimax Regret for Infinite-Memory Logistic Prediction

arXiv: https://arxiv.org/abs/2608.26515 · HTML: https://mlsanity.com/paper/2608.26515/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 39 references that are in the map.
- First posted on arXiv 27 Aug 2026.

## Builds on (most cited first, 3 of 3)

- [Logistic Regression: The Importance of Being Improper](https://mlsanity.com/paper/1803.09349/) (2018)
- [Logistic Regression Regret: What's the Catch?](https://mlsanity.com/paper/2002.02950/) (2020)
- [The Power of Second Order Methods for Sequence Preconditioning](https://mlsanity.com/paper/2605.08390/) (2026)

## Abstract (arXiv)

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.