Sharp Minimax Regret for Infinite-Memory Logistic Prediction
Abstract
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 ∑j≥1θjUt+1−j, the unknown coefficients obeying a summable envelope |θj|≤ rj, ∑jrj≤ 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 ΓT(r)=∑j≤ Tlog(1+nT,jrj2). One coordinate-localised Bayesian mixture achieves RT(r)≤ CΓT(r) for \emph{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 ΓT(r) is the minimax regret scale here, giving Θ(α−1log2T) for rj=Ae−αj and Θ(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(ΓT(r)) in polynomial time per round.
Related
- Expected Minimax Regret Rates for Adaptive LQG Control on Fixed Parameter Sets
- Expected Utility Regret Rule: Minimax and Bayes Optimal Portfolio Choice
- Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
- Closing the Log Gap: Minimax-Optimal Regret for Episodic RL
- Minimax regret and monotone optimality in multiple testing
BibTeX
@misc{aggarwal2026sharp,
title = {{Sharp Minimax Regret for Infinite-Memory Logistic Prediction}},
author = {Vaneet Aggarwal},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.26515},
eprint = {2608.26515},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.26515},
}
RIS
TY - UNPB
TI - Sharp Minimax Regret for Infinite-Memory Logistic Prediction
AU - Vaneet Aggarwal
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2608.26515
UR - https://arxiv.org/abs/2608.26515
AB - We determine the minimax cumulative log-loss regret of a finite-alphabet, exogenously driven source with genuinely infinite input memory: independent Rademacher inputs (U_t) are observed sequentially and the next binary mark has logit ∑_j≥1θ_jU_t+1−j, the unknown coefficients obeying a summable envelope |θ_j|≤ r_j, ∑_jr_j≤ B. At horizon T, lag j can move the logit by at most r_j and is exercised in only n_T,j=(T−j+1)_+ rounds, and the two limitations combine into the sum Γ_T(r)=∑_j≤ Tlog(1+n_T,jr_j^2). One coordinate-localised Bayesian mixture achieves R_T(r)≤ CΓ_T(r) for \emph{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 Γ_T(r) is the minimax regret scale here, giving Θ(α^−1log^2T) for r_j=Ae^−αj and Θ(T^1/(2s)) for r_j=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 O_B(Γ_T(r)) in polynomial time per round.
ER -