Metraipolis › archive › dc_ec688220b651
Sharp Minimax Regret for Infinite-Memory Logistic Prediction — arXiv:2608.26515
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.26515
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T16:15:49.343Z
- SHA-256 of the archived text
0adb7fdab55ee03e1ccb6e9a4048b5a7a6ee5ae27d517b77ec306238189f0fff- Stable URL of this page
https://metraipolis.com/documento/dc_ec688220b651
How to cite
Sharp Minimax Regret for Infinite-Memory Logistic Prediction — arXiv:2608.26515 — arXiv (en), https://arxiv.org/abs/2608.26515 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ec688220b651 (Metraipolis archive dc_ec688220b651, sha256 0adb7fdab55ee03e1ccb6e9a4048b5a7a6ee5ae27d517b77ec306238189f0fff)
BibTeX
@misc{dcec688220b651,
title = {Sharp Minimax Regret for Infinite-Memory Logistic Prediction — arXiv:2608.26515},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.26515},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ec688220b651; sha256 0adb7fdab55ee03e1ccb6e9a4048b5a7a6ee5ae27d517b77ec306238189f0fff},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.26515. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\sum_{j\ge1}\theta_jU_{t+1-j}$, the unknown coefficients obeying a summable envelope $|\theta_j|\le r_j$, $\sum_jr_j\le 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 $\Gamma_T(r)=\sum_{j\le T}\log(1+n_{T,j}r_j^{2})$. One coordinate-localised Bayesian mixture achieves $R_T(r)\le C\Gamma_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 $\Gamma_T(r)$ is the minimax regret scale here, giving $\Theta(\alpha^{-1}\log^{2}T)$ for $r_j=Ae^{-\alpha j}$ and $\Theta(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(\Gamma_T(r))$ in polynomial time per round.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-28 in cs.LG).
Categorie arXiv: Information Theory (cs.IT) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2608.26515 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T15:34:49.989Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).